2s11
2 pág.

2s11


DisciplinaModelagem de Sistemas de Producao15 materiais97 seguidores
Pré-visualização1 página
EPD065 - Modelagem de Sistemas de Produc¸a\u2dco
Prof. Carlos Roberto Vena\u2c6ncio de Carvalho
1a Prova - 20/09/2011 - 30 pontos
\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014
1a Questa\u2dco (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\u2dco 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\u2dces;
(b) (1,0 pontos) - defina os conjuntos necessa´rios e, se necessa´rio, defina constante(s) para a
formulac¸a\u2dco do problema;
(c) (1,0 pontos) - defina as varia´veis cont´\u131nuas 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\u2dco via´vel qualquer para o problema;
3. (1,5 pontos) - Desenhe o diagrama de Gantt desta soluc¸a\u2dco;
4. (1,5 pontos) - Quais os valores das varia´veis e do makespan desta soluc¸a\u2dco proposta?
2a Questa\u2dco (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\u2dco (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\u2dci 7 14 16 13
Table 2: Dados do problema 1|ri, d\u2dci|Cmax
Baseado no Modelo de Manne para o JobShop, escreva um modelo gene´rico de programac¸a\u2dco linear
inteira mista que calcula o makespan deste problema.
4a Questa\u2dco (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\u2dci 13 8 38 14 9 40 25
wi 2 6 3 3 4 2 9
5a Questa\u2dco (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\u131´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 \u2032) tal que, se {i, j} \u2282 U , enta\u2dco (i, j) \u2208 U \u2032.
(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´\u131tico entre os ve´rtices 0 e 7.
2