399_exercicios_pcpii_primeira_prova

Prévia do material em texto

EXERCÍCIOS PCP II – PROVA I 
 
 
 
Questão 1 - Duas tarefas, 1 e 2, devem ser sequenciadas com vistas à minimização do 
máximo atraso esperado, L. O atraso da tarefa j é dado por Lj = Cj-dj (Cj = dia de 
conclusão da tarefa i, dj = dia de entrega da tarefa j). A tarefa 1 deve ser entregue no dia 
2, e a tarefa 2 no dia 5. Os tempos de processamento das tarefas seguem as seguintes 
distribuições discretas: 
 
• P(X1=1) =1/5, P(X1=2) = 3/5, e P(X1=5) = 1/5 
 
• P(X2=3) = ¼, P(X2=4) = ½, P(X2=6) = ¼ 
 
Sequencie as tarefas 1 e 2 com vistas à minimização de L. 
 
 
Questão 2 – Os tempos de duas máquinas (M1e M2) são dados a seguir. Toda a tarefa 
deve ser antes executada em M1 e então em M2. Encontre a sequência que minimiza o 
makespan para estas tarefas. 
 
Tarefas M1 M2
1 11 23
2 23 26
3 25 45
4 14 59
5 12 57
6 15 51
7 48 52
8 36 32
9 26 23
10 29 36
11 38 34
12 25 19
13 23 28
14 10 26
15 9 13
Tempos das tarefas
 
 
 
 
 
Questão 3 – Considere a seguinte situação com 8 tarefas e data de entrega d=220. 
Sequencie as tarefas de forma a minimizar simultaneamente o tempo de atraso e de 
adiantamento. 
 
Tarefa 1 2 3 4 5 6 7 8
pi 36 56 42 14 36 25 42 39 
 
 
Questão 4 – Ordene as tarefas abaixo de forma a minimizar o número de tarefas 
atrasadas. 
Tarefa 1 2 3 4 5 6 7 8 9 10 11 12 
pj 5 8 7 9 6 4 12 14 10 5 6 7 
dj 15 23 6 14 50 80 82 32 75 45 30 48 
 
 
Questão 5 – Quatro tarefas são processadas através de três máquinas. Os presentes dados 
são pertinentes ao problema de programação. Encontre a sequência ótima para as tarefas 
tal que minimize o makespan. 
Tarefa M1 M2 M3
1 7 10 8
2 5 7 9
3 11 5 9
4 8 9 8
Tempos das Tarefas