2s11

Prévia do material em texto

EPD065 - Modelagem de Sistemas de Produc¸a˜o
Prof. Carlos Roberto Venaˆncio de Carvalho
1a Prova - 20/09/2011 - 30 pontos
——————————————————
1a Questa˜o (10 pontos):
Seja os dados de um problema do jobshop:
jobs oi : ma´quina (pi)
J1 o1 : 1(p1) o2 : 2(p2)
J2 o3 : 1(p3) o4 : 3(p4) o5 : 2(p5)
J3 o6 : 1(p6) o7 : 2(p7) o8 : 3(p8)
Table 1: Dados do problema J4|n = 3|Cmax
1. Escreva o problema (Modelo de Manne) sob a programac¸a˜o linear inteira mista que minimiza o
valor do makespan. Monte o modelo seguindo os passos:
(a) (1,0 pontos) - mostre o nu´mero de jobs, nu´mero de ma´quinas e nu´mero de operac¸o˜es;
(b) (1,0 pontos) - defina os conjuntos necessa´rios e, se necessa´rio, defina constante(s) para a
formulac¸a˜o do problema;
(c) (1,0 pontos) - defina as varia´veis cont´ınuas positivas;
(d) (1,0 pontos) - defina as varia´veis inteiras (bina´rias);
(e) (1,5 pontos) - escreva o problema com as constantes e varia´veis definidas nos itens anteriores;
2. (1,5 pontos) - Proponha uma soluc¸a˜o via´vel qualquer para o problema;
3. (1,5 pontos) - Desenhe o diagrama de Gantt desta soluc¸a˜o;
4. (1,5 pontos) - Quais os valores das varia´veis e do makespan desta soluc¸a˜o proposta?
2a Questa˜o (4 pontos):
1. (2,0 pontos) - Comente o modelo de Wagner para o problema do jobshop.
2. (2,0 pontos) - Comente o modelo indexado no tempo para o problema uma ma´quina.
3a Questa˜o (4 pontos):
Seja o problema de sequ¨enciamento em uma ma´quina mostrado na tabela.
Job J1 J2 J3 J4
ri 5 4 7 0
pi 5 7 4 4
d˜i 7 14 16 13
Table 2: Dados do problema 1|ri, d˜i|Cmax
Baseado no Modelo de Manne para o JobShop, escreva um modelo gene´rico de programac¸a˜o linear
inteira mista que calcula o makespan deste problema.
4a Questa˜o (4 pontos):
Resolva o problema abaixo utilizando o algoritmo de Smith.
1
Job J1 J2 J3 J4 J5 J6 J7
pi 4 3 8 2 4 7 5
d˜i 13 8 38 14 9 40 25
wi 2 6 3 3 4 2 9
5a Questa˜o (8 pontos):
Seja o grafo no orientado G(X,U) dado pelos conjuntos: X = {1, 2, 3, 4, 5, 6, 7} e
U = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 7}, {4, 5}, {4, 6}, {4, 7}, {5, 6}, {5, 7}, {6, 7}}, val-
orado nas arestas com os valores em ordem conforme aparece no conjunto U :
1, 4, 1, 6, 5, 2, 7, 5, 9, 1, 6, 4, 2, 6.
1. (1,0 pontos) - Desenhe o grafo graficamente;
2. (1,0 pontos) - determine uma a´rvore geradora mı´nima neste grafo;
3. (1,0 pontos) - determine um caminho mais curto entre os ve´rtices 1 e 7;
4. (1,0 pontos) - qual e´ o maior fluxo que pode passar entre os ve´rtices 1 e 7;
5. (1,0 pontos) - considere o grafo G(X,U ′) tal que, se {i, j} ⊂ U , enta˜o (i, j) ∈ U ′.
(a) (0,5 pontos) - a data mais cedo de cada ve´rtice;
(b) (0,5 pontos) - a data mais tarde de cada ve´rtice;
(c) (0,5 pontos) - as folgas associadas a` cada ve´rtice;
(d) (1,5 pontos) - o(s) caminho(s) cr´ıtico entre os ve´rtices 0 e 7.
2