Baixe o app para aproveitar ainda mais
Leia os materiais offline, sem usar a internet. Além de vários outros recursos!
MétodosSchedSPP20-05-10
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
* DEI - PUC/Rio * * DEI - PUC/Rio * Métodos para sequenciamento DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Um critério que pode ser interessante é minimizar o número de trabalhos em atraso (ex. Domino’s Pizza). O Método de Moore é simples e resolve de forma ótima esse problema. Minimizar o número de trabalhos em atraso DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Algoritmo 10 Passo - Seqüenciar os trabalhos, em ordem crescente de data prometida (regra MDP) 20 Passo - Procurar, na seqüência, o primeiro trabalho que fica atrasado. Se não houver trabalho com atraso, então a seqüência ótima já foi obtida; senão; 30 Passo - Considere todos os trabalhos da seqüência até o primeiro em atraso. Dentre estes (incluindo o primeiro em atraso), achar o trabalho com maior tempo de processamento, movendo-o para o final da programação. Todo trabalho já movido não será mais considerado para as próximas análises. 40 Passo - Repetir os passos 20 e 30, até que nenhum trabalho remanescente esteja em atraso. Minimizar o número de trabalhos em atraso: Método de Moore DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Ordenar crescentemente por data prometida DADOS Método de Moore: Exemplo DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * F tem maior pi dentre 1o atrasado e anteriores 1o atrasado F é retirado Método de Moore: Exemplo DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Maior pi dentre o 1o atrasado e anteriores 1o atrasado E é retirado Método de Moore: Exemplo DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Não há atrasados Terminado Método de Moore: Exemplo DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Os resultados vistos para uma única máquina não são facilmente estendidos para m máquinas. Por isso, veremos apenas métodos mais simples que se referem à minimização do makespan, num ambiente de oficina de fluxo. No caso de uma única máquina, é claro que qualquer que seja a seqüência, o makespan é o mesmo, mas não no caso de m máquinas. Minimizar o makespan, normalmente tem o efeito de aumentar a utilização das máquinas porque a oficina fica livre mais cedo para receber novos trabalhos, ou olhando de outro ângulo, os tempos ociosos da programação são minimizados. PROGRAMAÇÃO em DUAS MÁQUINAS DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Problema de Johnson Cada trabalho deverá ser executado primeiro na máquina 1 e depois na máquina 2. Demonstra-se que se o objetivo é minimizar o makespan, então a sequência ótima em cada uma das máquinas é a mesma. MÉTODO DE JOHNSON - Minimiza o Makespan 10 Passo - Listar os tempos de operação de cada trabalho, para cada uma das máquinas 20 Passo - Localizar o trabalho que possui o menor tempo de operação em qualquer uma das máquinas 30 Passo - Programar o trabalho encontrado no 20 passo O mais cedo possível, se o menor tempo pertencer a máquina 1 O mais tarde possível, se o menor tempo pertencer a máquina 2 40 Passo - Repetir o 20 e o 30 passo, até que todos os trabalhos sejam programados PROGRAMAÇÃO em DUAS MÁQUINAS: Método de Johnson DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Dados 10 Passo Programação pelo Método de Johnson 20 e 30 Passos - O menor tempo é da máquina 2 da tarefa A. Logo A vai para último e o problema fica reduzido a Seqüência até agora : ( _, _, _, A) PROGRAMAÇÃO em DUAS MÁQUINAS: Método de Johnson - Exemplo DEI - PUC/Rio Arbitrária T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 F D C B E A 0 6 10 13 20 28 37 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi F 6 9 4 1.50 6 6 -3 3 0 24 D 4 13 5 0.80 10 10 -3 3 0 50 C 3 16 5 0.60 13 13 -3 3 0 65 B 7 17 3 2.33 20 20 3 0 3 60 E 8 16 4 2.00 28 28 12 0 12 112 A 9 22 7 1.29 37 37 15 0 15 259 M É D I A 19.0 19.0 3.5 1.5 5.0 95.0 M Á X I M O 37 37 15 3 15 259 30 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness SPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 13 20 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 D 4 13 5 0.80 7 7 -6 6 0 35 D 4 13 5 F 6 9 4 1.50 13 13 4 0 4 52 F 6 9 4 B 7 17 3 2.33 20 20 3 0 3 60 B 7 17 3 E 8 16 4 2.00 28 28 12 0 12 112 E 8 16 4 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 M É D I A 18.0 18.0 2.5 3.2 5.7 88.8 M Á X I M O 37 37 15 13 15 259 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness WSPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 16 22 30 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 0.60 D 4 13 5 0.80 7 7 -6 6 0 35 SPT D 4 13 5 0.80 A 9 22 7 1.29 16 16 -6 6 0 112 18.0 A 9 22 7 1.29 F 6 9 4 1.50 22 22 13 0 13 88 F 6 9 4 1.50 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.00 B 7 17 3 2.33 37 37 20 0 20 111 SPT B 7 17 3 2.33 M É D I A 19.2 19.2 3.7 4.2 7.8 80.2 88.8 M Á X I M O 37 37 20 13 20 120 259 47 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness EDD T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD Data de Entrega (di) 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 Max. Tardiness (Ti) 15 15 20 15 F D C E B A 0 6 10 13 21 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 E 8 16 4 2.00 21 21 5 0 5 84 Arbitrária E 8 16 4 2.00 B 7 17 3 2.33 28 28 11 0 11 84 5.0 B 7 17 3 2.33 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 1.29 M É D I A 19.2 19.2 3.7 1.5 5.2 94.3 M Á X I M O 37 37 15 3 15 259 31 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness MOORE T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness JOHNSON Tarefa Tempo de Processamento Máquina 1 Máquina 2 A 4 2 B 7 7 C 6 5 D 6 8 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 pi/wi 0.00 0.00 0.00 0.00 0.00 0.00 3_MAQS T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness Arbitrária T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 F D C B E A 0 6 10 13 20 28 37 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi F 6 9 4 1.50 6 6 -3 3 0 24 D 4 13 5 0.80 10 10 -3 3 0 50 C 3 16 5 0.60 13 13 -3 3 0 65 B 7 17 3 2.33 20 20 3 0 3 60 E 8 16 4 2.00 28 28 12 0 12 112 A 9 22 7 1.29 37 37 15 0 15 259 M É D I A 19.0 19.0 3.5 1.5 5.0 95.0 M Á X I M O 37 37 15 3 15 259 30 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness SPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 13 20 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 D 4 13 5 0.80 7 7 -6 6 0 35 D 4 13 5 F 6 9 4 1.50 13 13 4 0 4 52 F 6 9 4 B 7 17 3 2.33 20 20 3 0 3 60 B 7 17 3 E 8 16 4 2.00 28 28 12 0 12 112 E 8 16 4 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 M É D I A 18.0 18.0 2.5 3.2 5.7 88.8 M Á X I M O 37 37 15 13 15 259 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness WSPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 16 22 30 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 0.60 D 4 13 5 0.80 7 7 -6 6 0 35 SPT D 4 13 5 0.80 A 9 22 7 1.29 16 16 -6 6 0 112 18.0 A 9 22 7 1.29 F 6 9 4 1.50 22 22 13 0 13 88 F 6 9 4 1.50 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.00 B 7 17 3 2.33 37 37 20 0 20 111 SPT B 7 17 3 2.33 M É D I A 19.2 19.2 3.7 4.2 7.8 80.2 88.8 M Á X I M O 37 37 20 13 20 120 259 47 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness EDD T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD Data de Entrega (di) 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 Max. Tardiness (Ti) 15 15 20 15 F D C E B A 0 6 10 13 21 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 E 8 16 4 2.00 21 21 5 0 5 84 Arbitrária E 8 16 4 2.00 B 7 17 3 2.33 28 28 11 0 11 84 5.0 B 7 17 3 2.33 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 1.29 M É D I A 19.2 19.2 3.7 1.5 5.2 94.3 M Á X I M O 37 37 15 3 15 259 31 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness MOORE T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness JOHNSON TAREFA TEMPO PROCESSAMENTO MÁQUINA 1 MÁQUINA 2 B 7 7 C 6 5 F D C E B A TAREFA MÁQUINA 1 MÁQUINA 2 Tempo de Fluxo 0 6 10 13 21 28 37 B 7 7 Data de Entrega 9 13 16 16 17 22 C 6 5 F D C B A E D 6 8 Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 pi/wi 0.00 0.00 0.00 0.00 0.00 0.00 3_MAQS T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness * DEI - PUC/Rio * * DEI - PUC/Rio * 40 Passo - Retorna ao 20 Passo, selecionado C e, no 3o Passo colocando-o em penúltimo lugar. Seqüência final: ( D, B, C, A) Eliminando C, o problema fica: Selecionando D no 2o Passo e colocando-o no primeiro lugar (3o Passo), o problema termina porque B ocupará o lugar restante PROGRAMAÇÃO em DUAS MÁQUINAS: Método de Johnson - Exemplo DEI - PUC/Rio Arbitrária T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 F D C B E A 0 6 10 13 20 28 37 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi F 6 9 4 1.50 6 6 -3 3 0 24 D 4 13 5 0.80 10 10 -3 3 0 50 C 3 16 5 0.60 13 13 -3 3 0 65 B 7 17 3 2.33 20 20 3 0 3 60 E 8 16 4 2.00 28 28 12 0 12 112 A 9 22 7 1.29 37 37 15 0 15 259 M É D I A 19.0 19.0 3.5 1.5 5.0 95.0 M Á X I M O 37 37 15 3 15 259 30 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness SPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 13 20 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 D 4 13 5 0.80 7 7 -6 6 0 35 D 4 13 5 F 6 9 4 1.50 13 13 4 0 4 52 F 6 9 4 B 7 17 3 2.33 20 20 3 0 3 60 B 7 17 3 E 8 16 4 2.00 28 28 12 0 12 112 E 8 16 4 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 M É D I A 18.0 18.0 2.5 3.2 5.7 88.8 M Á X I M O 37 37 15 13 15 259 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness WSPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 16 22 30 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 0.60 D 4 13 5 0.80 7 7 -6 6 0 35 SPT D 4 13 5 0.80 A 9 22 7 1.29 16 16 -6 6 0 112 18.0 A 9 22 7 1.29 F 6 9 4 1.50 22 22 13 0 13 88 F 6 9 4 1.50 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.00 B 7 17 3 2.33 37 37 20 0 20 111 SPT B 7 17 3 2.33 M É D I A 19.2 19.2 3.7 4.2 7.8 80.2 88.8 M Á X I M O 37 37 20 13 20 120 259 47 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness EDD T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD Data de Entrega (di) 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 Max. Tardiness (Ti) 15 15 20 15 F D C E B A 0 6 10 13 21 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 E 8 16 4 2.00 21 21 5 0 5 84 Arbitrária E 8 16 4 2.00 B 7 17 3 2.33 28 28 11 0 11 84 5.0 B 7 17 3 2.33 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 1.29 M É D I A 19.2 19.2 3.7 1.5 5.2 94.3 M Á X I M O 37 37 15 3 15 259 31 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness MOORE T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness JOHNSON TAREFA TEMPO PROCESSAMENTO MÁQUINA 1 MÁQUINA 2 B 7 7 C 6 5 F D C E B A TAREFA MÁQUINA 1 MÁQUINA 2 Tempo de Fluxo 0 6 10 13 21 28 37 B 7 7 Data de Entrega 9 13 16 16 17 22 C 6 5 F D C B A E D 6 8 Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 pi/wi 0.00 0.00 0.00 0.00 0.00 0.00 3_MAQS T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness Arbitrária T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 F D C B E A 0 6 10 13 20 28 37 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi F 6 9 4 1.50 6 6 -3 3 0 24 D 4 13 5 0.80 10 10 -3 3 0 50 C 3 16 5 0.60 13 13 -3 3 0 65 B 7 17 3 2.33 20 20 3 0 3 60 E 8 16 4 2.00 28 28 12 0 12 112 A 9 22 7 1.29 37 37 15 0 15 259 M É D I A 19.0 19.0 3.5 1.5 5.0 95.0 M Á X I M O 37 37 15 3 15 259 30 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness SPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 13 20 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 D 4 13 5 0.80 7 7 -6 6 0 35 D 4 13 5 F 6 9 4 1.50 13 13 4 0 4 52 F 6 9 4 B 7 17 3 2.33 20 20 3 0 3 60 B 7 17 3 E 8 16 4 2.00 28 28 12 0 12 112 E 8 16 4 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 M É D I A 18.0 18.0 2.5 3.2 5.7 88.8 M Á X I M O 37 37 15 13 15 259 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness WSPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 16 22 30 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 0.60 D 4 13 5 0.80 7 7 -6 6 0 35 SPT D 4 13 5 0.80 A 9 22 7 1.29 16 16 -6 6 0 112 18.0 A 9 22 7 1.29 F 6 9 4 1.50 22 22 13 0 13 88 F 6 9 4 1.50 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.00 B 7 17 3 2.33 37 37 20 0 20 111 SPT B 7 17 3 2.33 M É D I A 19.2 19.2 3.7 4.2 7.8 80.2 88.8 M Á X I M O 37 37 20 13 20 120 259 47 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness EDD T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD Data de Entrega (di) 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 Max. Tardiness (Ti) 15 15 20 15 F D C E B A 0 6 10 13 21 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 E 8 16 4 2.00 21 21 5 0 5 84 Arbitrária E 8 16 4 2.00 B 7 17 3 2.33 28 28 11 0 11 84 5.0 B 7 17 3 2.33 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 1.29 M É D I A 19.2 19.2 3.7 1.5 5.2 94.3 M Á X I M O 37 37 15 3 15 259 31 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness MOORE T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness JOHNSON TAREFA TEMPO PROCESSAMENTO MÁQUINA 1 MÁQUINA 2 B 7 7 C 6 5 F D C E B A TAREFA MÁQUINA 1 MÁQUINA 2 Tempo de Fluxo 0 6 10 13 21 28 37 B 7 7 Data de Entrega 9 13 16 16 17 22 D 6 8 Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 pi/wi 0.00 0.00 0.00 0.00 0.00 0.00 3_MAQS T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness Plan1 D B C A D B C A * DEI - PUC/Rio * * DEI - PUC/Rio * Um objetivo ao se programar tarefas com mais de duas máquinas pode ser minimizar o makespan Não há método simples, genérico e exato para programação de tarefas com mais de duas máquinas. Veremos: Uma modificação do Método de Johnson para aplicá-lo a 3 máquinas e que, numa situação particular, garante a otimalidade da solução) Um método heurístico para m máquinas (método de Campbell, Dudek and Smith) que não garante solução ótima. Programação em mais de duas máquinas DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Cada trabalho deverá ser executado primeiro na máquina 1, depois na máquina 2 e finalmente na máquina 3 Condição para que o método garanta solução ótima: O maior tempo na máquina do meio é menor, ou igual ao menor tempo em pelo menos uma das duas outras máquinas Programação em três máquinas: Método de Johnson para três máquinas DEI - PUC/Rio * DEI - PUC/Rio * * DEI - PUC/Rio * Procedimento Gera-se um problema de duas máquinas X e Y, a partir das máquinas 1, 2 e 3 de cada tarefa Máquina X - Terá como tempo de processamento, a soma dos tempos das máquinas 1 e 2 Máquina Y - Terá como tempo de processamento, a soma dos tempos das máquinas 2 e 3 Exemplo A condição é atendida, pois 11 > 9, o método de Johnson produzirá uma solução ótima Programação em três máquinas: Método de Johnson para três máquinas DEI - PUC/Rio Arbitrária T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 F D C B E A 0 6 10 13 20 28 37 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi F 6 9 4 1.50 6 6 -3 3 0 24 D 4 13 5 0.80 10 10 -3 3 0 50 C 3 16 5 0.60 13 13 -3 3 0 65 B 7 17 3 2.33 20 20 3 0 3 60 E 8 16 4 2.00 28 28 12 0 12 112 A 9 22 7 1.29 37 37 15 0 15 259 M É D I A 19.0 19.0 3.5 1.5 5.0 95.0 M Á X I M O 37 37 15 3 15 259 30 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness SPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 13 20 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 D 4 13 5 0.80 7 7 -6 6 0 35 D 4 13 5 F 6 9 4 1.50 13 13 4 0 4 52 F 6 9 4 B 7 17 3 2.33 20 20 3 0 3 60 B 7 17 3 E 8 16 4 2.00 28 28 12 0 12 112 E 8 16 4 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 M É D I A 18.0 18.0 2.5 3.2 5.7 88.8 M Á X I M O 37 37 15 13 15 259 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness WSPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 16 22 30 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 0.60 D 4 13 5 0.80 7 7 -6 6 0 35 SPT D 4 13 5 0.80 A 9 22 7 1.29 16 16 -6 6 0 112 18.0 A 9 22 7 1.29 F 6 9 4 1.50 22 22 13 0 13 88 F 6 9 4 1.50 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.00 B 7 17 3 2.33 37 37 20 0 20 111 SPT B 7 17 3 2.33 M É D I A 19.2 19.2 3.7 4.2 7.8 80.2 88.8 M Á X I M O 37 37 20 13 20 120 259 47 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness EDD T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD Data de Entrega (di) 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 Max. Tardiness (Ti) 15 15 20 15 F D C E B A 0 6 10 13 21 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 E 8 16 4 2.00 21 21 5 0 5 84 Arbitrária E 8 16 4 2.00 B 7 17 3 2.33 28 28 11 0 11 84 5.0 B 7 17 3 2.33 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 1.29 M É D I A 19.2 19.2 3.7 1.5 5.2 94.3 M Á X I M O 37 37 15 3 15 259 31 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness MOORE T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness JOHNSON TAREFA TEMPO PROCESSAMENTO MÁQUINA 1 MÁQUINA 2 A 4 2 B 7 7 C 6 5 TAREFA MÁQUINA 1 MÁQUINA 2 B 7 7 C 6 5 F D C B A E A 4 2 Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 Tempo de Fluxo® 0 7 13 17 Máquina 1 ® B C A Máquina 2 ® B C A Tempo de Fluxo® 0 7 14 19 21 pi/wi 0.00 0.00 0.00 0.00 0.00 0.00 3_MAQS Tarefa Tempo de processamento Máquina 1 Máquina 2 Máquina 3 A 18 9 16 B 12 3 11 C 10 2 20 D 1 4 15 Menor = 1 Maior= 9 Menor = 11 TAREFA MÁQUINA 1 MÁQUINA 2 B 7 7 C 6 5 F D C B A E A 4 2 Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 Tempo de Fluxo® 0 7 13 17 Máquina 1 ® B C A Máquina 2 ® B C A Tempo de Fluxo® 0 7 14 19 21 pi/wi 0.00 0.00 0.00 0.00 0.00 0.00 Arbitrária T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 F D C B E A 0 6 10 13 20 28 37 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi F 6 9 4 1.50 6 6 -3 3 0 24 D 4 13 5 0.80 10 10 -3 3 0 50 C 3 16 5 0.60 13 13 -3 3 0 65 B 7 17 3 2.33 20 20 3 0 3 60 E 8 16 4 2.00 28 28 12 0 12 112 A 9 22 7 1.29 37 37 15 0 15 259 M É D I A 19.0 19.0 3.5 1.5 5.0 95.0 M Á X I M O 37 37 15 3 15 259 30 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness SPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 13 20 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 D 4 13 5 0.80 7 7 -6 6 0 35 D 4 13 5 F 6 9 4 1.50 13 13 4 0 4 52 F 6 9 4 B 7 17 3 2.33 20 20 3 0 3 60 B 7 17 3 E 8 16 4 2.00 28 28 12 0 12 112 E 8 16 4 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 M É D I A 18.0 18.0 2.5 3.2 5.7 88.8 M Á X I M O 37 37 15 13 15 259 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness WSPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 16 22 30 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 0.60 D 4 13 5 0.80 7 7 -6 6 0 35 SPT D 4 13 5 0.80 A 9 22 7 1.29 16 16 -6 6 0 112 18.0 A 9 22 7 1.29 F 6 9 4 1.50 22 22 13 0 13 88 F 6 9 4 1.50 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.00 B 7 17 3 2.33 37 37 20 0 20 111 SPT B 7 17 3 2.33 M É D I A 19.2 19.2 3.7 4.2 7.8 80.2 88.8 M Á X I M O 37 37 20 13 20 120 259 47 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness EDD T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD Data de Entrega (di) 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 Max. Tardiness (Ti) 15 15 20 15 F D C E B A 0 6 10 13 21 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 E 8 16 4 2.00 21 21 5 0 5 84 Arbitrária E 8 16 4 2.00 B 7 17 3 2.33 28 28 11 0 11 84 5.0 B 7 17 3 2.33 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 1.29 M É D I A 19.2 19.2 3.7 1.5 5.2 94.3 M Á X I M O 37 37 15 3 15 259 31 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness MOORE T A R E F A A B C D E F A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD EDD Data de Entrega (di) 22 17 16 13 16 9 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 34 Max. Tardiness (Ti) 15 15 20 15 20 Número de Tarefas com Atrasos (Ti) 3 4 3 3 2 F D C E B A Tempo de Fluxo 0 6 10 13 21 28 37 Data de Entrega 9 13 16 16 17 22 F D C B A E Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 F D C A E B Tempo de Fluxo 0 6 10 13 22 30 37 Data de Entrega 9 13 16 22 16 17 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 A 9 22 7 1.29 22 22 0 0 0 154 A 9 22 7 2.00 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.33 B 7 17 3 2.33 37 37 20 0 20 111 B 7 17 3 1.29 M É D I A 19.7 19.7 4.2 1.5 5.7 87.3 M Á X I M O 37 37 20 3 20 154 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness JOHNSON TAREFA TEMPO PROCESSAMENTO MÁQUINA 1 MÁQUINA 2 A 4 2 B 7 7 C 6 5 TAREFA MÁQUINA 1 MÁQUINA 2 B 7 7 C 6 5 F D C B A E A 4 2 Tempo de Fluxo 0 6 10 13 20 29 37 Data de Entrega 9 13 16 17 22 16 Tempo de Fluxo® 0 7 13 17 Máquina 1 ® B C A Máquina 2 ® B C A Tempo de Fluxo® 0 7 14 19 21 pi/wi 0.00 0.00 0.00 0.00 0.00 0.00 3_MAQS TAREFA TEMPO PROCESSAMENTO MÁQUINA 1 MÁQUINA 2 MÁQUINA 3 A 18 9 16 B 12 3 11 C 10 2 20 D 1 4 15 MENOR = 1 MAIOR = 9 MENOR = 11 Tarefa Máquina X Máquina Y A 18 + 9 = 27 9 + 16 = 25 B 12 + 3 = 15 3 + 11 = 14 F D C B A E C 10 + 2 = 12 2 + 20 = 22 Tempo de Fluxo 0 6 10 13 20 29 37 D 1 + 4 = 5 4 + 15 = 19 Data de Entrega 9 13 16 17 22 16 Tempo de Fluxo® 0 7 13 17 Máquina 1 ® B C A Máquina 2 ® B C A Tempo de Fluxo® 0 7 14 19 21 pi/wi 0.00 0.00 0.00 0.00 0.00 0.00 * DEI - PUC/Rio * * DEI - PUC/Rio * O menor tempo é o da tarefa D na máquina X, que corresponde a 1a máquina: D vai para a primeira posição da sequência. O menor tempo é o da tarefa C na primeira máquina: C vai para a segunda posição na sequência, pois a primeira já foi ocupada por D. O menor tempo é o da tarefa B na 2a máquina: D vai para a última posição, completanto a sequência. Programação em três máquinas: Método de Johnson para três máquinas DEI - PUC/Rio Arbitrária T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 F D C B E A 0 6 10 13 20 28 37 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi F 6 9 4 1.50 6 6 -3 3 0 24 D 4 13 5 0.80 10 10 -3 3 0 50 C 3 16 5 0.60 13 13 -3 3 0 65 B 7 17 3 2.33 20 20 3 0 3 60 E 8 16 4 2.00 28 28 12 0 12 112 A 9 22 7 1.29 37 37 15 0 15 259 M É D I A 19.0 19.0 3.5 1.5 5.0 95.0 M Á X I M O 37 37 15 3 15 259 30 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness SPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 13 20 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 D 4 13 5 0.80 7 7 -6 6 0 35 D 4 13 5 F 6 9 4 1.50 13 13 4 0 4 52 F 6 9 4 B 7 17 3 2.33 20 20 3 0 3 60 B 7 17 3 E 8 16 4 2.00 28 28 12 0 12 112 E 8 16 4 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 M É D I A 18.0 18.0 2.5 3.2 5.7 88.8 M Á X I M O 37 37 15 13 15 259 34 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness WSPT T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 Data de Entrega (di) 22 17 16 13 16 9 C D F B E A 0 3 7 16 22 30 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi C 3 16 5 0.60 3 3 -13 13 0 15 C 3 16 5 0.60 D 4 13 5 0.80 7 7 -6 6 0 35 SPT D 4 13 5 0.80 A 9 22 7 1.29 16 16 -6 6 0 112 18.0 A 9 22 7 1.29 F 6 9 4 1.50 22 22 13 0 13 88 F 6 9 4 1.50 E 8 16 4 2.00 30 30 14 0 14 120 E 8 16 4 2.00 B 7 17 3 2.33 37 37 20 0 20 111 SPT B 7 17 3 2.33 M É D I A 19.2 19.2 3.7 4.2 7.8 80.2 88.8 M Á X I M O 37 37 20 13 20 120 259 47 LEGENDA Geram valores iguais Average Flow Time Makespan Average Lateness Maximum Lateness EDD T A R E F A A B C D E F Tempo Process. (pi) 9 7 3 4 8 6 CRITÉRIOS Arbitrário SPT WSPT EDD Data de Entrega (di) 22 17 16 13 16 9 STi = Atraso Total 30 34 47 31 Max. Tardiness (Ti) 15 15 20 15 F D C E B A 0 6 10 13 21 28 37 Carro Moto Moto Carro 0 30 40 0 10 40 Tarefa pi di wi pi/wi Ci Fi Li Ei Ti Fi*wi Tarefa pi di wi pi/wi F 6 9 4 1.50 6 6 -3 3 0 24 F 6 9 4 1.50 D 4 13 5 0.80 10 10 -3 3 0 50 D 4 13 5 0.80 C 3 16 5 0.60 13 13 -3 3 0 65 C 3 16 5 0.60 E 8 16 4 2.00 21 21 5 0 5 84 Arbitrária E 8 16 4 2.00 B 7 17 3 2.33 28 28 11 0 11 84 5.0 B 7 17 3 2.33 A 9 22 7 1.29 37 37 15 0 15 259 A 9 22 7 1.29 M É D I A 19.2 19.2 3.7 1.5 5.2 94.3 M Á X I M O 37 37 15 3 15 259 31 LEGENDA Geram valores iguais
Compartilhar
Materiais relacionados
20 pág.
Perguntas relacionadas
Perguntas Recentes
Compartilhar