Algoritmo de programação de máquinas individuais com penalidades distintas de
adiantamento e atraso
1. INTRODUÇÃO
Desde o início da difusão de princípios do JIT (Just-In-Time) ' que pode ser
considerado como um sistema de administração industrial relativo ao estoque ' ,
tem crescido a importância da diminuição do estoque no processamento de
produtos. Estamos fazendo mais um esforço nesse sentido, considerando como
característica-chave de nosso trabalho um dos elementos mais importantes do JIT
' evitar que produtos e componentes sejam produzidos ou entregues antes da data
correta (Groenevelt (1993)). Embora elementos como os erros, a diminuição do
tempo de preparação, a limpeza e a organização da fábrica também façam parte do
JIT, quer seja diretamente ou indiretamente, não estaremos considerando-os.
Sob o enfoque de uma das linhas de pesquisa da programação da produção (Baker
& Scudder (1990)), o JIT pode ter sua dimensão de programação caracterizada
através da penalização do término adiantado de ordens de produção. Devemos
lembrar que embora a programação do JIT geralmente esteja associada ao kanban,
muitos estudos teóricos têm sido feitos no sentido de utilizar a penalização do
término adiantado de ordens em sistemas que empurram a produção. Para boas
discussões acerca da aplicabilidade e definição de ambos os sistemas, vide
Silver et al. (1998) e Vollmann et al. (1997).
Uma das conseqüências mais importantes advindas das filosofias JIT é que
dependendo de certas condições, pode valer a pena manter uma máquina parada,
inserindo-se tempo de ociosidade entre a realização de duas ordens. Essa
característica, peculiar ao ambiente do tipo JIT, é válida enquanto os custos
provenientes de um suposto atraso não forem maiores do que os custos
provenientes do adiantamento. Portanto, uma metodologia que leve em
consideração ambos os custos ' de adiantamento e de atraso ' pode ser de grande
validade quando se deseja trabalhar num ambiente desse tipo. Para um maior
esclarecimento com relação a esse assunto, ver Colin (1997), onde o algoritmo
apresentado neste trabalho foi utilizado inicialmente.
Na próxima seção fazemos uma breve revisão sobre as principais definições
utilizadas neste trabalho e definimos formalmente nosso problema. Na seção 3
fazemos algumas discussões acerca de outros trabalhos que trataram do mesmo
tipo de problema. Na seção 4 apresentamos o algoritmo, enquanto que na seção 5
discutimos características de sua implementação computacional. Finalmente na
seção 6 apresentamos um exemplo numérico do uso do algoritmo.
2. CONCEITOS PRELIMINARES E DEFINIÇÃO DO PROBLEMA
Para o desenvolvimento do trabalho, utilizamos definições e notações clássicas,
de acordo com Morton & Pentico (1993). A seqüenciação é considerada como um
ordenamento das ordens de produção. Para um conjunto de ordens J={J1,¼,Jn},
deve-se encontrar a seqüência s=<s(1),s(2),¼, s(n)> com s(j)Î{1,2,¼,n} e s(j)¹s
(i) sempre que j¹i. Cada ordem Jj (j=1,¼,n), possui quatro valores inteiros
associados {pj,dj,wj,hj} que representam o tempo de processamento, a data de
entrega, a penalidade de atraso e a penalidade de adiantamento respectivamente.
A programação é definida como a determinação dos horários de início e de
término das ordens de uma dada seqüência. Para uma dada ordem Jj, existe um
intervalo de processamento [ej,ej+pj] onde ej e pj significam respectivamente o
horário efetivo de início do processamento e o tempo de processamento da ordem
Jj. No caso do problema de uma máquina, para duas ordens consecutivas Js(j) e
Js(j+1), com intervalos de processamento definidos por [es(j),es(j)+ps(j)] e
[es(j+1),es(j+1)+ps(j+1)], poderá haver intersecção entre os dois intervalos
apenas nos pontos extremos dos intervalos. Seja Ws(j) o período de ociosidade
antes da realização da ordem Js(j). O programa p(s)de um conjunto de ordens J,
é a determinação do horário efetivo de início de cada ordem, ou seja, p(s)=<es
(1),es(2),¼,es(n)>. Um programa parcial, pj(s ), é um programa que contém as j
primeiras ordens da seqüência s .
Estamos considerando que a seqüência já foi definida preliminarmente, e
portanto podemos omitir a seqüência s de nossa notação. A função diferença é
definida como
Lj=Cj'dj
, onde Cj=ej+pj é o horário de término da ordem Jj. Costuma-se separar a função
diferença quando ela é positiva e quando ela é negativa. Se negativa, é chamada
de adiantamento, e é definida como Ej=max(0,'Lj), enquanto que se positiva, é
chamada de atraso, e pode ser definida como Tj=max(0,Lj).
Estamos considerando o caso de uma única máquina que deve processar uma
seqüência de ordens s=<J1,J2,...,Jn>. O programa é realizado de maneira a
tentar cumprir as datas de entrega dj, sabendo-se que cada ordem demanda um
tempo pj para o seu processamento. Há possibilidade de inserção de tempo ocioso
Wj antes da elaboração de uma certa ordem Jj. Para penalidades hj>0 e wj>0, a
função-objetivo em questão pode ser definida como min g(p) = 
(hjEj + wjTj).
3. INSERÇÃO DE OCIOSIDADE
O primeiro trabalho a apresentar um algoritmo para inserção de ociosidade
pertence a Fry et al. (1987). De uma maneira bastante clara, os autores
formularam o problema de inserção de ociosidade no problema de atraso e
adiantamento com penalidades individuais, S(hjEj+wjTj), como um problema de
programação linear. Pela característica do tipo de problema, a solução acontece
em tempo O(n2). Algum tempo depois, Davis & Kanet (1993) propuseram um
outro algoritmo com tempo de solução no pior caso O(n2) para a solução do mesmo
problema.
De uma maneira provavelmente independente, Garey et al. (1988) também
propuseram um algoritmo de inserção de ociosidade no problema de atraso e
adiantamento sem penalidades, S (Ej+Tj), com tempo O(nlogn). Para o caso da
utilização de uma penalidade única para adiantamento e atraso, S wj(Ej+Tj), os
autores indicam como o algoritmo deveria ser formulado. Yano & Kim (1991)
elaboraram um algoritmo de inserção de ociosidade baseado na programação
dinâmica. A inserção de ociosidade é feita no problema com função-objetivo S
(hjEj+wjTj), onde é suposto que wj³hj³0. O tempo de solução no pior caso é O
(n2logn).
Todos os trabalhos supõem que os algoritmos sejam utilizados em uma seqüência
que foi definida preliminarmente.
4. ALGORITMO DE INSERÇÃO DE OCIOSIDADE
Nesta seção fazemos uma adaptação no algoritmo de inserção de ociosidade de
Garey et al. (1988) para a função-objetivo do tipo S (hjEj+wjTj). Esta seção e
a próxima seguem de forma bastante semelhante o desenvolvimento e a notação
utilizada por Garey et al.
O horário desejado de início da ordem Jj é definido como aj=dj'pj. O horário
efetivo de início de uma dada ordem é denotado por ej. Um bloco de ordens Bi
(i=1,2,...,l) é definido como uma seqüência parcial que é programada sem
inserção de ociosidade entre as ordens da mesma. Matematicamente pode-se dizer
que uma dada seqüência de ordens M = <Jm1, Jm2, ..., Jmj> é um bloco de ordens
se ek+pk=ek+11 (para m1£k< mj), (para m1>1)
e <formula/> (para mj<n).
Assumimos que um programa completo pn(s) possui l blocos <B1,...,Bl> (1£i£ l;
l£ n). Um esquema gráfico dos conceitos de bloco é apresentado na Figura_1.
Cada bloco Bi é particionado em 2 subconjuntos, denominados Atrasado(i) e
Adiantado(i). Seja uma ordem JjÎ
Bi
. JjÎ
Atrasado
(i) se ej>aj e JjÎ
Adiantado
(i) se ej£
aj
, ou seja, se JjÎAtrasado(i), reduzindo-se ej, reduz-se o atraso de Jj e se
JjÎAdiantado(i), reduzindo-se ej, aumenta-se o adiantamento de Jj.
Adicionalmente define-se H(i) = <formula/> e W(i) = [/
img/fbpe/pope/v20n1/a04img05.gif].
Para se representar um bloco Bi, serão necessários apenas as definições dos
índices extremos, ou seja, primeiro(i) que é o índice do primeiro elemento de
Bi e último(i) que é o índice do último elemento de Bi. As ordens
intermediárias são facilmente identificadas pois são relacionadas com a
primeira e com a última.
4.1. VISÃO GERAL DO ALGORITMO
A idéia central do algoritmo está na construção e movimentação dos blocos, onde
essa movimentação acontece sempre fazendo com que as ordens do mesmo sejam
antecipadas. Sempre acontece uma antecipação do bloco pois as ordens
adicionadas ao bloco estão sempre atrasadas ou no horário desejado. Se as datas
de entrega forem suficientemente dispersas, cada bloco será formado por apenas
uma ordem. Como isso obviamente não ocorre sempre, existem períodos de
conflito, onde a capacidade disponível na máquina não é suficiente para
processar todas as ordens de modo que suas datas de entrega sejam atendidas.
Quando isso acontece, os adiantamentos e atrasos penalizados das ordens do
bloco em consideração são avaliados procurando-se por uma oportunidade de se
diminuir a penalidade total. Deve-se observar que um bloco contém ordens
atrasadas e adiantadas e uma movimentação do bloco para mais cedo faz com que
as ordens adiantadas fiquem mais adiantadas, enquanto que as ordens atrasadas
atrasem menos ou passem a estar adiantadas. Neste trabalho uma ordem que se
inicia no horário desejado é considerada adiantada.
Para esse fim, o algoritmo é iniciado fazendo com que a primeira ordem seja
finalizada em sua data de entrega. Isso pode não ser possível, visto que a
ordem já pode estar virtualmente atrasada ' mesmo que ela seja iniciada no
instante inicial, ela vai atrasar. Verifica-se se a próxima ordem pode ser
terminada em sua data de entrega. Aqui pode acontecer duas coisas: um novo
bloco ser formado ou a ordem ser adicionada ao último bloco formado. Um novo
bloco será formado caso o término da última ordem do último bloco seja anterior
ao início desejado da ordem em consideração. Por outro lado, a ordem será
incluída no último bloco formado, caso o término da última ordem do último
bloco seja posterior ou igual ao horário de início desejado da ordem em
consideração. Neste último caso, haverá uma ponderação entre todas as ordens
pertencentes ao bloco formado com a nova ordem. Se a nova ordem adicionada
estiver atrasada e esse atraso, juntamente com os outros atrasos penalizados
pertencentes ao bloco for maior que os adiantamentos penalizados, então o bloco
é movimentado para mais cedo enquanto a penalização total diminui. Este
procedimento é realizado até a última ordem ser programada.
4.2. DETALHAMENTO DO ALGORITMO
Para um melhor entendimento do algoritmo, ele pode ser considerado como tendo
duas partes: a primeira, para construção de blocos e a segunda, para
antecipação de blocos. De maneira mais precisa, podemos dizer que a primeira
parte do algoritmo ' construção de blocos ' tem início simplesmente
programando-se o horário efetivo de início de J1 igual ao horário desejado de
início de J1, isto é, e1=a1. Para um programa parcial pj(s) já realizado,
programa-se Jj+1+1 conforme dois casos:
Caso 1: ej+pj£
aj
+1. Programa-se Jj+1 para começar em aj+1. Nesse caso Jj+1 não possui nem
atraso nem adiantamento pois é inserido um período de ociosidade e portanto g
(pj+1(s))=g(pj(s)).
Caso 2:ej+pj>aj+1. Programa-seJj+1 para começar emej+pj. Nesse casoJj+1 possui
atraso. A ordem Jj+1 é inserida no bloco Bl (onde l é o índice do último bloco,
isto é, o bloco em análise) e no conjunto Atrasado(l).
Uma propriedade-chave, enunciada por Garey et al., mantida pelo algoritmo, é
que para cada bloco BiÎpj(s), ou W(i)<H(i) ou eprimeiro(i)=0 (para i=l=1).
Quando a próxima ordem (Jj+1+1) é programada, apenas o último bloco pode sofrer
alguma alteração. Essa alteração pode fazer com que o último bloco tenha pelo
menos uma das seguintes propriedades: (a) W(l)<H(l), (b) W(l)³H(l) ou (c)
eprimeiro(i)=0.
A segunda parte do algoritmo, de antecipação dos blocos, acontece considerando
que se W(l)<H(l) ou eprimeiro(l)=0, então não se toma nenhuma ação e o programa
pj+1(s) transforma-se no programa corrente. Por outro lado, se W(l)=H(l) e
eprimeiro(l)¹0, então pode-se movimentar o bloco Blinteiro, sem afetar o valor
da função-objetivo do programa. Caso contrário, se W(l)>H(l) e eprimeiro(l)¹0,
pode-se antecipar o bloco Bl inteiro, fazendo com que o valor da função-
objetivo do programa diminua. Essas movimentações são feitas até um dos 3 casos
seguintes acontecer:
Caso a. eprimeiro(l)=0. Ocorrerá somente se l=1. Caso ocorra, o bloco Bl não
pode ser movimentado para mais cedo pois ele estará começando no horário 0;
Caso b. para algum JjÎBl, ej=aj. A ordem é transferida do conjunto Atrasado(l)
para Adiantado(l) e W(l)<H(l). Nesse caso, outras movimentações de Bl só irão
aumentar o valor da função-objetivo. Caso contrário, se a ordem for transferida
de Atrasado(l) para Adiantado(l) e W(l)³H(l), continua-se a movimentação;
Caso c. eprimeiro(l)=eúltimo
(l'1)
+púltimo(l'1). O bloco Bl é unido ao bloco Bl'1. Se eprimeiro(l'1)¹0 e W(l'1)+W
(l)³H(l'1)+H(l), continua-se a movimentação dos blocos unidos l'1 e l. Se
eprimeiro(l'1)¹0 e W(l'1)+W(l)<H(l'1)+H(l), deve-se parar a movimentação pois a
função-objetivo só irá piorar.
O programa resultante é pj+1(s). O algoritmo faz sucessivas aplicações do
procedimento acima formando os programas p2(s),p3(s),...,pn(s).
4.3. ANÁLISE DO ALGORITMO
A demonstração que o algoritmo descrito proporciona um programa ótimo para uma
seqüência predefinida no caso sem penalidades é apresentada em Garey et al.
(1988, p. 338). O teorema adiante prova que o algoritmo descrito aqui garante a
otimização do problema em consideração.
Teorema(baseado no teorema 2 deGareyet al.). Para qualquer j, o programa
parcial pj(s) calculado pelo algoritmo tem o mínimo S(hjEj+wjTj) dentre todos
os programas possíveis para as primeiras j ordens.
Demonstração: Ver apêndice.
Quando W(i)=H(i) para pelo menos um Bi(i=1,2,...,l), podemos perceber que
existem infinitos mínimos. Neste caso, o algoritmo proposto irá programar o
início do bloco o mais cedo possível.
Deve-se lembrar que a ordem iniciada no horário desejado pertence ao conjunto
Adiantado e portanto, na melhor condição possível ' condição de g(p)=0 ' ,
todas as ordens estariam nos conjuntos Adiantado. Para o entendimento da
propriedade-chave enunciada por Garey et al., ela pode ser dividida em duas
partes como segue:
Parte 1: Quando eprimeiro(i)=0. Só acontece quando i=l=1. Não há ociosidade
antes do primeiro bloco e conseqüentemente não há como diminuir os atrasos. A
relação W(l)³H(l) pode ser verdadeira pois não há como movimentar o bloco para
mais cedo.
Parte 2: Quando eprimeiro(l)¹0. Para um bloco l com uma ordem apenas, ej=aj,
sendo primeiro(l)=j. A ordem Jj pertence ao conjunto Adiantado(l) e W(l)<H(l).
Para um bloco l com diversas ordens, vamos aceitar que até a última ordem do
mesmo, Jj, a condição W(l)<H(l) seja verdadeira. O acréscimo de Jj+1 a Bl pode
acontecer devido à aj+1=ej+1 ou aj+1<ej+1, isto é, ou a ordem começa no horário
desejado, ou a ordem está atrasada. Quando aj+1=ej+1, seguramente a
desigualdade W(l)<H(l) se mantém após o acréscimo de Jj+1 ao bloco Bl, pois
Jj+1 vai para o conjunto Adiantado(l). Quando aj+1<ej+1, Jj+1 vai para o
conjunto Atrasado(l) e isso pode nos trazer um dos três resultados a seguir:
(1) wj+1+W(l)>H(l), a propriedade-chave não é mantida e portanto o bloco deve
ser movimentado para mais cedo pois eprimeiro(l)¹0. O bloco é movimentado para
mais cedo até que eprimeiro(l)=0 ou wj+1+W(l)<H(l). Se houver diversos blocos,
pode ser necessário haver união dos blocos Bl e Bl'1 mais de uma vez. As uniões
serão realizadas até que pelo menos uma das duas condições de paralização do
algoritmo seja alcançada; (2) wj+1+W(l)<H(l), a ordem Jj+1 vai para o conjunto
Atrasado(l), mas de maneira contrária ao caso (1), a propriedade-chave é
mantida. Uma movimentação para mais cedo fará com que a função-objetivo piore
pois a soma das penalidades de adiantamento é maior que a soma das penalidades
de atraso; (3) wj+1+W(l)=H(l), a ordem Jj+1 vai para o conjunto Atrasado(l) e
as movimentações podem ser feitas pois não irão afetar o valor da função-
objetivo. O que se perde quando se adianta as ordens do conjunto Adiantado(l),
se ganha com a diminuição do atraso das ordens do conjunto Atrasado(l). A
movimentação será feita até que o bloco esteja se iniciando no horário mais
cedo possível. O raciocínio precedente pode ser generalizado por indução.
5. IMPLEMENTAÇÃO DO ALGORITMO UTILIZANDO ESTRUTURAS DE FILAS DE PRIORIDADE
Uma implementação eficiente do algoritmo da seção anterior pode ser baseada na
estrutura de dados denominada fila de prioridade. Sem a utilização das filas de
prioridades, o tempo de solução do algoritmo é O(n2), enquanto que com a
utilização das filas de prioridades é O(nlogn).
De acordo com Tarjan (1983, p. 33), uma fila de prioridade é uma estrutura de
dados abstrata consistindo de uma coleção de itens, cada um dos quais possuindo
um valor real associado denominado chave.
Para cada bloco de ordens Bi é mantida uma fila de prioridade P(i), que
determinará o quanto cada um poderá ser movimentado. Cada fila de prioridade
deverá manter dois valores de cada item: o primeiro é o índice das ordens
pertencentes a Atrasado(i); o segundo é o valor equivalente a
ej'aj
para cada índice j (a quantidade máxima que ej pode ser diminuída, enquanto
diminui o atraso de Jj).
O algoritmo pode ser elaborado considerando-se seis operações com filas de
prioridades:
Operação 1. CriaFilaDePrioridade(P). Cria uma fila de prioridade
vazia denominada P;
Operação 2. EncontraMin(P). Encontra um item de mínima chave na fila
de prioridade P e apresenta essa chave sem remover o item da fila de
prioridade;
Operação 3. ApagaMin(P). Encontra um item de mínima chave na fila de
prioridade P. Apresenta seu índice e remove o item da fila de
prioridade;
Operação 4. Insere(j,x,P). Insere o item j com chave x na fila de
prioridade P;
Operação 5. Une(P1,P2). Une as filas de prioridades P1 e P2 de itens
disjuntos em uma nova fila de prioridade que transforma-se em P1. A
fila de prioridade P2 torna-se vazia;
Operação 6. AdicionaParaTodasChaves(x,P). Adiciona-se x para todas as
chaves dos itens pertencentes à fila de prioridade P.
O pseudocódigo utilizado para se inserir a ociosidade em uma seqüência de
ordens com os horários de início desejados é apresentado a seguir. Ele é
dividido em duas partes, a de construção e a de antecipação de blocos. A Figura
2 mostra a primeira parte do algoritmo enquanto que a Figura_3 mostra a segunda
parte do algoritmo.
Após o término do algoritmo, cada ordem jÎJ pode ter seu horário efetivo de
início definido pela seguinte equação:
Garey et al. e Tarjan discutem tempos de solução computacional, mostrando que
as operações com fila de prioridade descritas anteriormente demandam um tempo
de no máximo O(logn) para sua realização. Portanto o algoritmo possui tempo O
(nlogn).
6. EXEMPLO
Suponha um conjunto de ordens já seqüenciado, definido pela Tabela_1, com todas
ordens disponíveis no instante zero. Queremos saber se a inserção de ociosidade
nessa dada seqüência pode promover uma diminuição no valor da função-objetivo.
Por uma questão de comparação, será calculado inicialmente o valor da função-
objetivo da seqüência sem a inserção de ociosidade. A Tabela_2 ilustra alguns
passos intermediários para esse caso.
O valor da função-objetivo em análise sem a inserção de ociosidade é dado por S
(hjEj+wjTj)=32907. Utilizando-se o algoritmo de inserção de ociosidade, podemos
facilmente construir a Tabela_3.
Os valores intermediários dos horários efetivos de início das ordens obtidos
pelo algoritmo são os seguintes: e1=178; e1=178, e2=223; e1=91, e2=136; e1=91,
e2=136, e3=237; e1=91, e2=136, e3=237, e4=285; e1=91, e2=136, e3=237, e4=285,
e5=358. Os blocos existentes após o algoritmo ter sido finalizado são os
seguintes: B1={J1,J2} e B2={J3,J4,J5}.
Os blocos indicam que as ordens devem ser produzidas sem a inserção de
ociosidade entre as ordens do mesmo bloco. O valor da função-objetivo nesse
caso é equivalente a S(hjEj+wjTj)=18870, que de acordo com o teorema é
comprovadamente o mínimo valor alcançado para a seqüência definida
inicialmente.
7. APÊNDICE: DEMONSTRAÇÃO DO TEOREMA
Para a demonstração do teorema, por uma questão de simplicidade notacional,
será omitida a seqüência na qual o programa está sendo construído, ou seja, o
programa parcial pj(s) será representado por pj. A representação do valor da
função objetivo de um programa parcial até as primeiras j ordens será g(pj) =
<formula/> (hkEk+wkTk) e de um programa completo será
g(pj) = <formula/> (hkEk+wkTk).
Teorema(baseado no teorema 2 de Garey et al. (1988)). Para qualquer j, o
programa parcial pj calculado pelo algoritmo tem o mínimo g(pj) dentre todos os
programas possíveis para as primeiras j ordens.
Demonstração. Como hipótese de indução, assumimos que em j e em Æ o teorema é
verdadeiro. Portanto, só falta provar que para j+1 o teorema também é
verdadeiro. Seja <formula/> algum programa das
primeiras j+1 ordens e seja ek e <formula/> os
horários efetivos de início da ordem Jk em pj e [/img/fbpe/pope/v20n1/
a04img11.gif], respectivamente. Devemos considerar dois casos:
Caso sem atraso. Se ej+Pj£ aj+1, então para pj+1 não haverá aumento na função-
objetivo,g(pj+1) = g(pj), pois a ordem Jj+1 é programada para iniciar em aj+1.
Também podemos perceber que Ej+1=Tj+1=0. Mas g([/img/fbpe/pope/v20n1/
a04img09.gif])³g(pj) pois <formula/> sem a ordem Jj+1,
é um programa para as primeiras j ordens, tendo a função-objetivo com valor de
no mínimo g(pj) pela hipótese de indução. Como [/img/fbpe/pope/v20n1/
a04img12.gif]³0 e <formula/>³0, podemos concluir que g
(<formula/>)³g(pj+1) fazendo com que o teorema seja
verdadeiro.
Caso com atraso. Se ej+1>aj+1, então haverá atraso e portanto aumento no valor
da função-objetivo. Seja pj+1 o programa definido pelo algoritmo formado por pj
acrescido da ordem Jj+1 iniciada em ej+1= ej+ Pj
.
Então g(pj+1) = g(pj) + wj+1Tj+1. Para a comparação entre g(pj+1) e g([/img/
fbpe/pope/v20n1/a04img09.gif]) podemos considerar dois casos distintos:
Caso 1 com atraso: Se <formula/>³ej+1, então g(pj) +
wj+1(<formula/>'aj+1)³g(pj) + wj+1(ej+1'aj+1) o que
nos leva a g(<formula/>)³g(pj+1), fazendo com que o
teorema se mantenha verdadeiro.
Caso 2 com atraso: No último caso <formula/>>ej+1.
Podemos considerar que haja 4 hipóteses de alteração do programa [/img/fbpe/
pope/v20n1/a04img09.gif] com relação ao programa pj+1: (1) não há união de
blocos e nenhuma ordem passa do conjunto Atrasado(l) para o conjunto Adiantado
(l); (2) há união de blocos; (3) há passagem de pelo menos uma ordem do
conjunto Atrasado(l) para o conjunto Adiantado(l); (4) há uma combinação das
hipóteses anteriores. Na hipótese 1, o último bloco do programa [/img/fbpe/
pope/v20n1/a04img09.gif],BlÎ<formula/>, teria todas as
ordens adiantadas em uma quantidade equivalente a ej+1' [/img/fbpe/pope/v20n1/
a04img14.gif]. Nesse caso g(BlÎ<formula/>)=[/img/fbpe/
pope/v20n1/a04img15.gif], e considerando que [/img/fbpe/pope/v20n1/
a04img16.gif]= Ek + (ej+1' <formula/>) e [/img/fbpe/
pope/v20n1/a04img17.gif]= Tk' (ej+1' <formula/>),
podemos dizer que <formula/>.
Como <formula/> H (l) ' W (l) > 0, ej+1 ' [/img/fbpe/
pope/v20n1/a04img14.gif] > 0 e g(BlÎpj+1) = [/img/fbpe/pope/v20n1/
a04img20.gif], na hipótese 1, g(<formula/>)> g(pj+1) e
portanto o teorema é verdadeiro. Como na hipótese 2 há união de blocos, e pela
propriedade-chave juntamente com a hipótese de indução sabemos que H(l)+H(l-
1)>W(l)+W(l-1), o mesmo raciocínio da hipótese 1 pode ser aplicado e portanto o
teorema continua sendo verdadeiro. Na hipótese 3, há passagem de pelo menos uma
ordem do conjunto Atrasado(l) para o conjunto Adiantado(l), mantendo H(l)>W(l)
e fazendo com que o raciocínio da hipótese 1 possa ser aplicado, sendo assim o
teorema verdadeiro. Finalmente, na hipótese 4 acontece uma combinação dos casos
anteriores, fazendo mais uma vez com que o teorema continue sendo verdadeiro.
