Home   |   Structure   |   Research   |   Resources   |   Members   |   Training   |   Activities   |   Contact

EN | PT

BrBRCEEn0101-74382000000100004

BrBRCEEn0101-74382000000100004

National varietyBr
Country of publicationBR
SchoolEx-Tech-Multi Sciences
Great areaEngineering
ISSN0101-7438
Year2000
Issue0001
Article number00004

Javascript seems to be turned off, or there was a communication error. Turn on Javascript for more display options.

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 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. 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; 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 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) 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 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 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. acontece quando i=l=1. Não ociosidade antes do primeiro bloco e conseqüentemente não como diminuir os atrasos. A relação W(l)³H(l) pode ser verdadeira pois não 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 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, 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 união de blocos e nenhuma ordem passa do conjunto Atrasado(l) para o conjunto Adiantado (l); (2) união de blocos; (3) passagem de pelo menos uma ordem do conjunto Atrasado(l) para o conjunto Adiantado(l); (4) 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 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, 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.


Download text