Exercícios de Sequenciamento GABARITO - prof Adriana

Prévia do material em texto

Exercícios P3
1-Um técnico conserta equipamentos que uma empresa que aluga. A chegada de equipamentos para reparo não é regular, de modo que freqüentemente existe um acúmulo de trabalhos para o técnico. Para cada equipamento na oficina, há um custo diário de perda de oportunidade de aluguel do equipamento. Para cada serviço, o técnico prometeu uma data para entrega. Num dado momento, os equipamentos a serem consertados são conforme a tabela abaixo e o técnico sabe que não receberá outros serviços antes que termine esses que já estão na oficina. Como o técnico trabalha sozinho, só pode consertar um equipamento de cada vez e, quando começa um reparo, tem que terminá-lo antes de começar outro. 
	Serviço
	Tempo de reparo
(dias)
	Valor do aluguel (KR$)
	Data prometida
	1
	5
	3
	8
	2
	3
	4
	25
	3
	9
	6
	12
	4
	7
	10
	20
	5
	2
	1
	15
Em cada um dos itens abaixo, explique como você concluiu, ou cite o método que você utilizou e a propriedade que ele tem.
a) Se o objetivo do técnico for minimizar o número médio de equipamentos na oficina, qual a seqüência em que os serviços deverão ser executados? Explique.
Resposta:
SPT (Shortest Processing Time) – Minimiza o tempo total de espera, o tempo total de fluxo e também o número médio de trabalhos no sistema.
Explicação: Slides 14 e 15 da aula 1.1 Regras de Sequenciamento.
	Serviço
	Tempo de reparo
(dias)
	Valor do aluguel (KR$)
	Data prometida
	5
	2
	1
	15
	2
	3
	4
	25
	1
	5
	3
	8
	4
	7
	10
	20
	3
	9
	6
	12
Sequência: 5-2-1-4-3.
b) Se o objetivo for minimizar o custo total de aluguel perdido; qual deve ser a seqüência de execução dos reparos? Explique.
Resposta:
WSPT (Weighted Shortest Processing Time) – Minimiza o tempo total de fluxo ponderado pela medida de interesse, nesse caso, o custo total de aluguel perdido.
Explicação: Slides 16 da aula 1.1 Regras de Sequenciamento.
	Serviço
	Tempo de reparo
(dias)
	Valor do aluguel (KR$)
	Data prometida
	pi/wi
	4
	7
	10
	20
	7/10=0,70
	2
	3
	4
	25
	¾=0,75
	3
	9
	6
	12
	9/6=1,50
	1
	5
	3
	8
	5/3=1,66
	5
	2
	1
	15
	2/1=2,00
Sequência: 4-2-3-1-5.
c) Segundo os dados do problema, pode o técnico fazer os reparos em uma seqüência tal que todos sejam concluídos até a sua data prometida? Responda usando uma regra de seqüenciamento e explique como chegou à conclusão.
Resposta:
EDD (Earliest Due Date) – Minimiza a defasagem máxima ou o atraso máximo, se o atraso for inevitável.
Explicação: Slides 19 da aula 1.1 Regras de Sequenciamento.
	Serviço
	Tempo de reparo
(dias)
	Valor do aluguel (KR$)
	Data prometida
	1
	5
	3
	8
	3
	9
	6
	12
	5
	2
	1
	15
	4
	7
	10
	20
	2
	3
	4
	25
Sequência: 1-3-5-4-2.
Não é possível fazer os reparos em uma sequência tal que todos sejam concluídos até a sua data prometida pois o método EDD, que tem como objetivo minimizar a defasagem máxima, não consegue atender à esta restrição (vide datas de término). Para minimizar o número de trabalhos em atraso, poderia ser aplicado o método de Moore.
2- 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 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
	40
	50
	80
	2
	70
	
	140
	3
	10
	
	70
	4
	
	40
	120
	5
	
	
	60
a) O dono da oficina começa a trabalhar assim que chega e 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).
Resposta:
Método de Johnson – O objetivo é minimizar o makespan.
Explicação: Slides 13 a 16 da apresentação 1.2 Métodos para Sequenciamento.
1º Passo – Verificar a condição para que o método garanta a 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.
	
	Tempos de processamento (minutos)
	Identificação
	Seção A
	Seção B
	Seção C
	1
	40
	50
	80
	2
	70
	
	140
	3
	10
	
	70
	4
	
	40
	120
	5
	
	
	60
	
	Menor=10
	Maior=50
	Menor=60
A condição é satisfeita.
2º Passo – Gera-se um problema de duas máquinas X e Y, a partir das máquinas A, B e C de cada trabalho. Máquina X terá como tempo de processamento, a soma dos tempos das seções A e B. Máquina Y terá como tempo de processamento, a soma dos tempos das seções B e C.
	
	Tempo de processamento (minutos)
	Identificação
	Seção A+B
	Seção B+C
	1
	90
	130
	2
	70
	140
	3
	10
	70
	4
	40
	160
	5
	0
	60
3º Passo – Localizar o trabalho que possui o menor tempo de operação em qualquer uma das máquinas.
	
	Tempo de processamento (minutos)
	Identificação
	Seção A+B
	Seção B+C
	1
	90
	130
	2
	70
	140
	3
	10
	70
	4
	40
	160
	5
	0
	60
4º Passo - Programar o trabalho encontrado no 3º passo o mais cedo possível, se o menor tempo pertencer a máquina X, e o mais tarde possível, se o menor tempo pertencer a máquina Y.
	
	Tempo de processamento (minutos)
	Identificação
	Seção A+B
	Seção B+C
	1
	90
	130
	2
	70
	140
	3
	10
	70
	4
	40
	160
	5
	0
	60
Sequência 5, _, _, _, _.
5º Passo - Repetir o 3º e 4º passo, até que todos os trabalhos sejam programados.
	
	Tempo de processamento (minutos)
	Identificação
	Seção A+B
	Seção B+C
	1
	90
	130
	2
	70
	140
	3
	10
	70
	4
	40
	160
Sequência 5, 3, _, _, _.
	
	Tempo de processamento (minutos)
	Identificação
	Seção A+B
	Seção B+C
	1
	90
	130
	2
	70
	140
	4
	40
	160
Sequência 5, 3, 4, _, _.
	
	Tempo de processamento (minutos)
	Identificação
	Seção A+B
	Seção B+C
	1
	90
	130
	2
	70
	140
Sequência 5, 3, 4, 2, _.
	
	Tempo de processamento (minutos)
	Identificação
	Seção A+B
	Seção B+C
	1
	90
	130
Sequência 5, 3, 4, 2, 1.
b) Quanto tempo ele vai demorar na oficina antes de poder ir para casa? Deixe indicado como você chegou ao resultado.
Resposta: 470 minutos.
c) Qual a seqüência que miniminiza a ociosidade das seções.
Resposta:
A mesma sequência feita pelo método de Johnson pois minimizar o makespan tem o efeito de aumentar a utilização das máquinas porque a oficina fica livre mais cedo para receber novos trabalhos, assim, os tempos ociosos da programação são minimizados. 
3- A equipe de manutenção da Darkness S.A., uma companhia distribuidora de energia elétrica, tem num determinado momento, diversas chamadas de rompimento de rede para serem atendidas. Quando um rompimento ocorre, um técnico se dirige rapidamente ao local e faz uma avaliação da situação. Como os técnicos avaliadores são muito experientes e o cadastro de componentes da rede é muito bem feito, o supervisor de turno consegue boas estimativas para o tempo de reparo e para a multa que a empresa paga por minuto de interrupção de fornecimento de energia àquele trecho da rede. Os tempos para reparo incluem o tempo de movimentação e não dependem da seqüência. Num determinado momento, o supervisor tem os seguintes chamados já avaliados:
	j (chamado)
	pj (tempo para reparo em horas)
	vj (multa por minuto de interrupção KR$)
	(Para uso do aluno, se precisar)
	1
	2
	1
	
	2
	5
	3
	
	3
	1
	2
	
	4
	4
	5
	
	5
	3
	10
	
 
(a) Diante dos dados acima, qual a sequência de reparos que o supervisor deve mandar a equipe realizar para minimizar o valor pago em multas (deixe indicado os cálculos necessários)? É possível existir outra sequência que dê o mesmo mínimo valor total de multa? 
Resposta:
WSPT (Weighted Shortest Processing Time) – Minimiza o tempo total de fluxo ponderado pela medida de interesse, nesse caso, o valor pago em multas.
Explicação: Slides 16 da aula 1.1 Regras de Sequenciamento.
1º Passo – Calcular o pj/vj
	j (chamado)
	pj (tempo para reparo em horas)
	vj (multa porminuto de interrupção KR$)
	pj/vj
	1
	2
	1
	2,00
	2
	5
	3
	1,66
	3
	1
	2
	0,50
	4
	4
	5
	0,80
	5
	3
	10
	0,30
2º Passo – Ordenar em ordem crescente pelo pj/vj
	j (chamado)
	pj (tempo para reparo em horas)
	vj (multa por minuto de interrupção KR$)
	pj/vj
	5
	3
	10
	0,30
	3
	1
	2
	0,50
	4
	4
	5
	0,80
	2
	5
	3
	1,66
	1
	2
	1
	2,00
Sequência: 5-3-4-2-1.
Como não houve empate na relação pj/vj, apenas esta sequência minimiza o tempo médio de fluxo ponderado e, portanto, o valor total pago em multas.
(b) Qual esse mínimo valor total pago em multas neste caso? 
Resposta:
Calculando a multa:
	j (chamado)
	pj (tempo para reparo em horas)
	vj (multa por minuto de interrupção KR$)
	pj/vj
	Interrupção (h)
	Multa (KR$)
	5
	3
	10
	0,30
	3
	30
	3
	1
	2
	0,50
	4
	8
	4
	4
	5
	0,80
	8
	40
	2
	5
	3
	1,66
	13
	39
	1
	2
	1
	2,00
	15
	15
Mínimo valor total pago em multas: 30+8+40+39+15 = 132 KR$
4- [3 pontos] Uma fábrica de materiais esportivos fabrica produtos que seguem diversos roteiros de fabricação. A tabela abaixo fornece as informações relativas às quatro encomendas que tem para a semana e precisam ser programados. Suponha que hoje seja 10 de novembro e que a fábrica funciona sete dias por semana. Suponha que os materiais para todas as encomendas já estão disponíveis e que a regra de “primeira a chegar, primeira a ser processada” é utilizada em todas as seções da fábrica. Todas as seções estarão ociosas quando a programação começar a ser executada hoje (10 de novembro).
	Encomenda
	Data de chegada
	Roteiro de passagem nas seções
	Tempo de processamento na S1
	Tempo de processamento na S2
	Tempo de processamento na S3
	A
	10 nov
	1-3-2
	1
	3
	1
	B
	10 nov
	2-3-1
	2
	2
	2
	C
	12 nov
	3-2-1
	3
	1
	2
	D
	14 nov
	3-2-1
	1
	3
	1
a) [2 pontos] Construa um gráfico de Gantt representando os tempos de processamento e ociosos em cada uma das seções para a programação descrita acima.
Resposta:
	
	10nov
	11nov
	12nov
	13nov
	14nov
	15nov
	16nov
	17nov
	18nov
	19nov
	20nov
	S1
	A
	
	B
	
	C
	D
	S2
	B
	A
	
	C
	D
	
	S3
	
	A
	B
	C
	D
	
b) [1 ponto] Quantos dias cada trabalho ficará esperando na fila para processamento na Seção 2?
Resposta:
A – 2 dias
B – 0 dias
C - 6 dias
D – 7 dias
102030405060708090100110120130140150160170180190200210220230240250260270280290300310320330340350360370380390400410420430440450460470
5
3A
4
2
1ABC
C
C
BC
AC