Exercícios Sequenciamento GABARITO - prof Adriana

Prévia do material em texto

LIS TA: E XERCÍCIOS SO BRE SEQ UENCIAM ENTO E PRO GRAM AÇ ÃO DE TAREFAS 
 
As soluções estão em fonte branco para serem vistas apenas após 
concluir o exercício 
 
Além das explicações a seguir, veja as apresentações exibidas em aula e as notas 
abaixo. Primeiramente reveja as apresentações feitas em aula e depois as notas abaixo. 
Antes de ver as soluções dos exercícios resolvidos, tente resolvê-los. 
 
• Método de Johnson 
O método de Johnson é um exemplo de método para sequenciamento de n trabalhos (ou 
tarefas), só que não mais em uma única máquina (ou centro de trabalho), mas sim, em 
duas máquinas (ou centros de trabalho). Supõe-se que todos os trabalhos têm que passar 
por ambas as máquinas numa mesma dada ordem (é claro que podemos sempre tratar o 
caso em que alguns trabalhos só precisam passar pela primeira máquina, ou só pela 
segunda, bastando para isso, definirmos o tempo de processamento como sendo zero). 
 
O objetivo do Método de Johnson é minimizar o “makespan”, ou seja, o tempo decorrido 
desde que se inicia o processamento primeiro trabalho a ser processado, na primeira 
máquina, até que se termine o processamento do último trabalho na segunda máquina. 
Observe que no caso de uma única máquina o makespan é o mesmo independentemente 
da sequência. No caso de duas máquinas, demonstra-se que numa sequência que 
minimiza o makespan, os trabalhos devem passam pela segunda máquina na mesma 
sequência de passagem pela primeira. Caso a segunda máquina termine um trabalho e 
não possa iniciar o seguinte porque a primeira máquina ainda não o liberou, esse tempo 
ocioso (espera da segunda máquina para que o trabalho termine na primeira) será 
somado ao makespan. Para eliminar os tempos ociosos na segunda máquina seria 
interessante tentar processar, na primeira máquina, os trabalhos em ordem crescente do 
tempo de processamento nela e processar na segunda máquina, os trabalhos em ordem 
decrescente de tempo de processamento nela. Isso tenderia a fazer com que a segunda 
máquina fique sem tempo ocioso. Mas se a ordem de passagem na segunda máquina tem 
que ser a mesma da passagem na primeira, em geral isso não é possível. O Método de 
Johnson resolve esse conflito. 
 
O método de Johnson serve para minimizar o makespan de trabalhos que passam por 
duas máquinas em oficina de fluxo pura. Entretanto, é interessante notar, que em alguns 
casos, esse método pode ser usado para minimizar o makespan de trabalhos que passam 
sequencialmente em três máquinas. Um caso desses, é quando o maior tempo de 
processo na máquina do meio é menor, ou igual ao menor tempo de processo na 
primeira máquina, ou menor, ou igual ao menor tempo de processo na última máquina. 
Se qualquer uma (ou ambas) dessas duas condições ocorrer, criamos duas máquinas 
fictícias somando, para cada trabalho, o tempo de processamento na máquina do meio ao 
tempo na primeira máquina e, também, ao tempo na última. Agora, considerando um 
problema com apenas duas máquinas e esses novos tempos de processamento e, a ele, 
aplicamos o Método de Johnson convencional. O resultado é a sequência ótima. 
 
2 
Exercício 1 
Sejam os trabalhos abaixo a serem processados sequencialmente em duas máquinas 
conforme abaixo: 
 
Trabalho Tempo de processamento 
 na máquina A 
Tempo de processamento 
 na máquina B 
1 180 40 
2 20 160 
3 120 100 
4 60 200 
5 240 80 
 
a) Supondo que os trabalhos chegam todos à oficina na mesma hora. Qual a sequência 
de processamento dos trabalhos que permite a oficina terminar todos os trabalho o 
mais cedo possível? 
Resp.: 
Aplicando-se o método de Johnson obtém-se a sequência {2, 4, 3, 5, 1}. 
 
b) Supondo que os tempos estão em minutos, e que a oficina abre às 7h e só fecha 
quando termina todos os trabalhos, a que hora ela irá fechar? 
Resp.: 
Construindo o Gráfico de Gantt relativo à sequência ótima acima, é possível verificar que 
o término do último trabalho na máquina B se dá após 660 minutos depois do início 
do primeiro trabalho na máquina A, ou seja o makespan é de 11h. Se a oficina abre às 
7 h ela deverá fechar às 18h. 
Através do Gráfico de Gantt é possível verificar ainda que a máquina B fica ociosa 
durante uma hora esperando que a máquina A termine o trabalho 1 para ela poder 
processá-lo. 
 
c) Considere ainda, a aplicação do Método de Johnson a uma situação com mais uma 
máquina, C, entre as duas outras (i.e. depois de A e antes de B), na qual os tempos de 
processamento de cada trabalho igual à média dos seus tempos em A e B. Pode-se 
aplicar o Método de Johnson para achar a sequência que minimiza o makespan? Caso 
negativo; porque não se pode garantir que o método vai gerar uma sequência ótima? 
Caso positivo; qual a sequência ótima? 
 
Resp.: 
Não se pode garantir que a aplicação do Método de Johnson para três máquinas irá 
produzir a sequência de makespan mínimo porque o maior tempo na máquina C será 
maior do que o menor tempo na máquina A e maior do que o menor tempo na 
máquina B (basta verificar que o tempo do trabalho 1 na máquina C é 110 > 40 > 20). 
 
 
3 
Exercício 2 
 
Seja o Problema de Sequenciamento de Johnson com 3 máquinas, abaixo: 
 
Trabalho Tempo de processamento 
 na máquina A 
Tempo de processamento 
 na máquina B 
Tempo de processamento 
 na máquina C 
1 90 5 20 
2 10 10 80 
3 60 20 50 
4 30 15 100 
5 120 18 40 
6 100 20 30 
 
Pergunta-se: 
a) A aplicação do Método de Johnson para 3 máquinas garante uma sequência ótima? 
Por que? 
Resp.: 
Sim; porque o maior tempo na máquina do meio, B, (p3,B = p6,B = 20) é igual ao menor 
tempo em uma das máquinas (máquina C) (p1,C = 20). 
b) Aplique o Método ao Problema. 
Resp.: 
Veja o problema modificado para aplicação do Método de Johnson para duas máquinas 
abaixo, obtido somando-se o tempo de cada trabalho na máquina do meio aos 
respectivos tempos nas máquinas anterior e posterior. 
Trabalho Tempo de processamento 
 na máquina A 
Tempo de processamento 
 na máquina C 
1 95 25 
2 20 90 
3 80 70 
4 45 115 
5 138 58 
6 120 50 
 
A sequência ótima é {2, 4, 3, 5, 6, 1}. O gráfico de Gantt correspondente é apresentado 
abaixo. Repare os tempos ociosos nas máquinas B e C. 
45040035030025020015010050
165342
4 165
42 1653
32
C
B
A
435100 
4 
 
Exercício 3 
Um pequeno porto tem um único berço de atracação e recebe navios de diferentes tamanhos 
e com diferentes tipos de carga. Num determinado dia encontram-se em espera para descarga os 
seguintes navios, todos sujeitos a multas. 
 
Identificação 
do navio 
Tempo p/ 
descarga 
Multa por 
hora 
1 12 100 
2 24 400 
3 6 300 
4 36 200 
5 18 100 
 
(a) Qual a sequência de descarga dos navios que minimiza a multa total? Qual o total de 
multa a ser pago? Qual o tempo médio de espera? 
 
Resp.: 
Utilizando o MTPP ou WSPT conforme tabela abaixo, tem-se a sequência de navios 3, 2, 
1, 4 e 5 ou 3, 2, 1, 5 e 4 que minimizam o tempo total de fluxo e de trabalhos em sistema 
com base em um fator de ponderação. O total da multa a ser paga é de 21.600 e o tempo 
médio de espera é de 31,2 horas ou 31 horas e 12 minutos conforme valores 
apresentados na tabela a seguir. 
 
Identificação 
do navio
Tempo p/ 
descarga
Multa por 
hora
pj/wj Sequência
Tempo de 
espera
Multa
1 12 100 0,12 3 30 3000
2 24 400 0,06 2 6 2400
3 6 300 0,02 1 0 0
4 36 200 0,18 4 42 8400
5 18 100 0,18 4 78 7800
Tempo de 
espera 
médio
Multa total
31,2 21600 
 
 
 
(b) Qual a sequência que minimiza a o tempo médio de espera? Qual o tempo médio de 
espera? Qual o total de multa a ser pago? 
 
Resp.: 
Utilizando o STP ou MTP tem-se a sequência 3, 1, 5, 2 e 4 que minimizam o tempo total 
de fluxo e de trabalhos em sistema, e consequentemente o tempo médio de espera. O 
tempo médio de espera é de 24 horas e o total de multa a ser pago é de 28.800 conforme 
valores apresentados na tabela a seguir. 
 
5 
Identificação 
do navio
Tempo p/ 
descarga
Multa por 
hora
Sequência
Tempo de 
espera
Multa
1 12 100 2 6 600
2 24 400 4 36 14400
3 6 3001 0 0
4 36 200 5 60 12000
5 18 100 3 18 1800
Tempo de 
espera 
médio
Multa total
24 28800 
 
 
 
Exercício 4 
Uma oficina faz a manutenção de uma frota de ônibus padronizada com um único 
modelo utilizado em todas as linhas da empresa. Para reduzir a probabilidade de colocar 
nas suas linhas menos ônibus do que os contratos de concessão da prefeitura exigem (e 
com isso, ter que pagar elevadas multas), a empresa mantém em sua frota um número de 
ônibus um pouco maior do que o necessário. Dessa forma, quando um ônibus quebra, 
ela o substitui por um ônibus que não esteja em uso e envia o ônibus quebrado para 
reparo em sua oficina. Como o investimento representado por um ônibus é substancial, o 
número de ônibus em excesso ao necessário para seus contratos não é muito grande. Por 
isso o objetivo da gerência da oficina é ter o máximo de ônibus prontos para entrar em 
uso (o que obviamente, equivale a ter o menor número possível de ônibus na oficina). 
Supondo que o tempo necessário para o conserto de cada ônibus que entra na oficina 
pode ser estimado com precisão; qual deve ser a regra de seqüenciamento para atender o 
objetivo da gerência. 
Resp.: 
Como o número de ônibus que se dispõe é constante, maximizar o número de ônibus 
fora da oficina é o mesmo que minimizar o número na oficina. Sabemos que a regra 
MTP (ou SPT) minimiza o número médio de trabalhos no sistema, por isso a regra de 
seqüenciamento a usar deveria ser a de consertar os ônibus na ordem crescente de seus 
tempos de conserto. 
 
 
Exercício 5 
Uma pequena empresa de consultoria tem sete contratos de projetos (dados na tabela 
abaixo), todos com datas de entrega estabelecidas medidas em dias a partir de hoje. Os 
consultores são um pequeno grupo que só pode desenvolver um projeto por vez e, uma 
vez iniciado, um projeto não pode ser interrompido. De acordo com os termos do 
contrato, os consultores pagarão multa fixa de $3000, por cada projeto em atraso (sem 
importar quão atrasado). Responda às perguntas abaixo indicando como você chegou à 
sua resposta e como você tem certeza de que é a melhor solução citando o nome do 
método, ou explicando por que. 
6 
Qual a sequência de execução dos projetos que maximiza a receita líquida (i.e. receita 
total menos o total pago em multas) do grupo? [Dica: repare que a receita não muda com 
a sequência e que interessa apenas o número de trabalhos atrasados] 
 
Projeto 1 2 3 4 5 6 7 
Duração 2 5 6 8 11 12 14 
Valor do projeto 1 4 2 10 12 10 16 
Data para entrega 6 12 30 19 12 18 24 
 
 
Resp.: 
Como a receita não muda com a sequência de projetos, apenas a multa que pode variar 
com a quantidade de projetos em atraso, o melhor método a ser aplicado no 
sequenciamento dos projetos é o Método de Moore. Isso porque tal método visa 
minimizar o número de trabalhos em atraso, e com isso a quantidade de multas fixas 
recebidas pela empresa de consultoria. 
 
7 
Aplicando-se a regra do EDD (Earliest due date)
Projeto 1 2 5 6 4 7 3
Duração 2 5 11 12 8 14 6
Valor do projeto 1 4 12 10 10 16 2
Data para entrega 6 12 12 18 19 24 30
Data de término 2 7 18 30 38 52 58
Defasagem -4 -5 6 12 19 28 28
Projeto 1 2 6 4 7 3 5
Duração 2 5 12 8 14 6 11
Valor do projeto 1 4 10 10 16 2 12
Data para entrega 6 12 18 19 24 30 12
Data de término 2 7 19 27 41 47 58
Defasagem -4 -5 1 8 17 17 46
Projeto 1 2 4 7 3 5 6
Duração 2 5 8 14 6 11 12
Valor do projeto 1 4 10 16 2 12 10
Data para entrega 6 12 19 24 30 12 18
Data de término 2 7 15 29 35 46 58
Defasagem -4 -5 -4 5 5 34 40
Projeto 1 2 4 3 5 6 7
Duração 2 5 8 6 11 12 14
Valor do projeto 1 4 10 2 12 10 16
Data para entrega 6 12 19 30 12 18 24
Data de término 2 7 15 21 32 44 58
Defasagem -4 -5 -4 -9 20 26 34
Como o projeto 5 é o primeiro na sequência que possui atraso, dentre os três 
primeiros ele é o que possui maior duração e por isso é transferido para o final da 
sequência.
Refazendo os cálculos com a saída do projeto 6, tem-se o projeto 7 como o próximo 
na sequência que possui atraso. Dentre os quatro primeiros, ele coincidentemente 
é o que possui maior duração e por isso é transferido para o final da sequência.
Refazendo os cálculos com a saída do projeto 5, tem-se o projeto 6 como o próximo 
na sequência que possui atraso. Dentre os três primeiros, ele coincidentemente é 
o que possui maior duração e por isso é transferido para o final da sequência.
Dessa forma, garante-se que a sequência 1, 2, 4, 3, 5, 6 e 7 minimiza o número de 
projetos em atraso e consequentemente o total de multa recebida pela empresa. 
 
 
 
 
 
8 
Exercício 6 
O departamento jurídico de uma empresa cuida de processos de cobrança judicial cujo 
tempo de resolução é muito bem previsível. A chegada de processos não é regular, de 
modo que frequentemente existe um acúmulo de processos relativos a cobranças cujos 
valores são bem variados. O objetivo é minimizar o valor global dos processos ainda não 
resolvidos visto que quanto maior o valor desse estoque de processos, maior o custo de 
oportunidade em que a empresa está incorrendo. Num dado momento, os processos a 
serem processados são conforme a tabela abaixo. 
Trabalho Tempo de processo 
(semanas) 
Valor do processo (kR$) 
1 5 3 
2 3 4 
3 9 6 
4 7 10 
5 15 1 
(a) Qual a sequência ótima? Explique por que essa sequência minimiza o custo de 
oportunidade do dinheiro que a empresa tem por receber (Dica: o custo de oportunidade 
do dinheiro dos processos ainda não resolvido é a taxa de custo de oportunidade do 
capital vezes o valor total dos processos ainda não resolvidos). Na sua explicação 
mencione o nome do método que você utilizou e qual a medida de desempenho que ele 
garantidamente otimiza, ou demonstre que ele otimiza a medida de desempenho. 
Repostas não explicadas poderão ser desconsideradas. 
 
Resp.: 
A sequência ótima de resolução dos trabalhos é 4, 2, 3, 1 e 5. A regra de sequenciamento 
utilizada foi a Menor Tempo de Processamento Ponderado (MTPP ou WSTP), visto que 
ela garante o menor número de projetos em sistema considerando um fator de 
ponderação tal como o valor do processo em espera ou custo de oportunidade. Na tabela 
a seguir encontram-se os valores obtidos para essa resposta. 
 
Trabalho
Tempo de 
processo 
(semanas)
Valor do 
processo 
(kR$)
pj/wj Sequência
Custo de 
oportunidade
1 5 3 1,67 4 57
2 3 4 0,75 2 28
3 9 6 1,50 3 60
4 7 10 0,70 1 0
5 15 1 15,00 5 24
169 
 
 
(b) Qual a sequência que minimiza o número médio de processos no escritório. Diga 
brevemente como chegou a ela, ou cite o nome e a propriedade do método utilizado 
que lhe permitiu chegar à sequência ótima. 
 
9 
Resp.: 
Utilizando o STP ou MTP tem-se a sequência 2,1,4,3 e 5 que minimizam o tempo total 
de fluxo e de trabalhos em sistema, e consequentemente o tempo médio de espera deles. 
Na tabela a seguir encontram-se os valores obtidos para essa resposta. 
 
Trabalho
Tempo de 
processo 
(semanas)
Valor do 
processo 
(kR$)
Sequência
Tempo de 
espera
1 5 3 2 3
2 3 4 1 0
3 9 6 4 15
4 7 10 3 8
5 15 1 5 24
10 
 
 
 
Exercício 7 
Em uma oficina de lanternagem de automóveis os trabalhos são realizados em 
duas seções: lanternagem e pintura. Atualmente quatro automóveis estão para reparo na 
oficina e os tempos de processamento (em horas) previstos para cada seção são os 
seguintes 
Auto Lanternagem Pintura 
1 10 6 
2 5 8 
3 12 9 
4 7 8 
a) Qual a sequência de reparo dos autos que permite a oficina terminar todos os 
trabalhos o mais cedo possível? 
b) Considerando a sequência respondida em a), quantas horas serão necessárias do 
início do primeiro reparo até terminar todos os reparos nesses quatro automóveis? 
Resp.: 
(a) Uma sequência que minimize o makespan é o que se deseja. Como visto em aula, o 
Método de Johnson produz tal sequência. Aplicando temos: 
1. Menor tempo = 5 do auto (tarefa) 2 na lanternagem (máquina 1), ⇒ (2, x, x, x), 
elimina-se a tarefa 2. 
2. Menor tempo no restante do problema = 6 da tarefa 1 na máquina 2 (pintura), ⇒ (2, 
x, x, 1), elimina-sea tarefa 1. 
3. Menor tempo no restante do problema = 7 da tarefa 4 na máquina 1, ⇒ (2, 4, x, 1), 
elimina-se a tarefa 4. 
A tarefa restante é colocada na única posição restante nos fornecendo a 
sequência ótima (2, 4, 3, 1) 
 
(b) Há quem prefira fazer um gráfico de Gantt. Aqui fica mais fácil calcular os tempos de 
término na máquina 1 e os inícios e términos na máquina 2: 
Máquina 1: C2,1 = 0+5 = 5; C4,1 = 5+7 =12; C3,1 = 12+12= 24; C1,1 = 24+10 =34; 
1
0 
Máquina 2: C2,2 = C2,1 +8 = 13; C4,2 = Max{ C2,2; C4,1 }+8 =13+8=21; C3,2 = Max{ 
C4,2; C3,1 }+9 =24+9= 33; C1,2 = = Max{ C3,2; C1,1 }+6 =34+6= 40 
 
 
Exercício 8 
Uma oficina de reparos tem três seções. A primeira seção faz o diagnóstico, a segunda 
uma limpeza e a terceira o conserto em si. Em alguns casos, o problema é óbvio e não há 
necessidade de diagnóstico. Em outros casos, a limpeza é desnecessária. É fácil de se 
estimar com boa precisão os tempos que cada trabalho toma em cada seção, pois uma 
tipologia já foi bem estabelecida. Num dia os trabalhos a serem executados na oficina são 
conforme abaixo. 
 
 Tempos de processamento (minutos) 
Identificação Seção A Seção B Seção C 
1 50 30 80 
2 90 140 
3 30 60 
4 50 120 
5 60 
 
a) O dono da oficina só vai para casa quando todos os trabalhos forem concluídos e ele 
quer ir embora o mais cedo possível. Em que ordem ele deve processar os 
trabalhos? (Diga por que você pode garantir que a sua resposta é ótima, citando o 
método utilizado e deixando indicado como realizou o método). 
 
 
Resp.: 
O Método de Johnson garante uma solução ótima para o sequenciamento de tarefas em 
3 máquinas, se o maior tempo da máquina do meio (Seção B = 50) é menor que o tempo 
ou na primeira máquina (Seção A = 0) ou na última máquina (Seção C = 60), o que 
acontece nesse problema. Nesse caso, a sequência ótima é 5, 3, 4, 1 e 2, isso porque o 
menor tempo entre as máquinas X e Y é o da tarefa 5 na máquina X, logo ela deve ser a 
primeira atividade; o próximo menor tempo é da tarefa 3 na máquina X e por isso é a 
segunda atividade; o menor tempo das atividades restantes encontra-se na atividade 4 e 
na máquina X, por isso essa é a terceira; o menor tempo das duas atividades restantes 
encontra-se na atividade 1 na máquina X, e por isso ela é a quarta na sequência; ficando 
por último a atividade 2. Esses dados encontram-se apresentados na tabela a seguir. 
 
1
1 
Identificação Seção A Seção B Seção C
Máquina 
X (A+B)
Máquina 
Y (B+C)
Sequência
1 50 30 80 80 110 4
2 90 140 90 140 5
3 30 60 30 60 2
4 50 120 50 170 3
5 60 0 60 1
Tempos de processamento 
(minutos)
 
 
 
 
 
b) Quanto tempo ele vai demorar na oficina antes de poder ir para casa? Deixe indicado 
como você chegou ao resultado. 
 
Resp.: 
O tempo total que o dono deverá ficar na oficina é de 460 minutos, visto que esse é o 
somatório do tempo de processamento de todos os trabalhos na Seção C que é a única 
que fica sem tempo ocioso conforme o gráfico a seguir. 
 
A
B
C
0 5 10 15 20 25 30 35 40 45
2
2
4
4
1
1
5 3
3 1
 
 
 
 
 
Exercício 9 
Uma loja tem um único balcão que atende a todos os clientes que nela entram. Os clientes 
chegam de forma aleatória e são atendidos em ordem de chegada. Cada cliente deve demorar não 
mais do que X minutos na loja (desde que chega até ter seu atendimento concluído). Caso 
demore mais do que X minutos, o tempo excedente é considerado atraso e, caso demore menos, 
o que faltar para X minutos é considerado adiantamento. Explique por que ao atender os clientes 
na mesma ordem em que chegam a gerência estará minimizando o atraso do cliente que mais 
ficar atrasado, ou caso não resulte nenhum cliente atrasado, a gerência estará maximizando o 
adiantamento do cliente que resultar menos adiantado. 
Resp.: Segundo o enunciado, para cada cliente, a data prometida é o instante X minutos após 
sua chegada à loja. Como os clientes são atendidos por ordem de chegada, são também atendidos 
em ordem crescente de data prometida. Ora, sabemos da teoria que o seqüenciamento em ordem 
de crescente de data prometida minimiza a máxima defasagem (lateness), ou seja, minimiza o 
maior atraso da sequência ou, se não houver atraso, maximiza o menor adiantamento. 
 
 
 
1
2 
Exercício 10 (método de Campbell, Dudek e Smith) 
 
Máquina → 
Trabalho↓ 
A B C D 
1 3 7 6 4 
2 7 6 2 9 
3 5 4 3 10 
4 4 2 5 3 
 
Resp.: (a) Uma sequência que minimize o makespan é o que se deseja. Como visto em 
O método gera apenas 3 sequências conforme abaixo 
 Sequência / Makespan 
Primeira sequência (1, 3, 2, 4) / 42 
Segunda sequência (4, 1, 2, 3) / 43 
Terceira sequência (3, 2, 1, 4) / 39 
Com outro método obtive a sequência (3, 2, 4, 1) / 38 (a melhor, talvez a ótima)