ModWagner
3 pág.

ModWagner


DisciplinaModelagem de Sistemas de Producao15 materiais97 seguidores
Pré-visualização1 página
1.6.7 - Modelos da Programac¸a\u2dco Inteira Mixta 59
1.6.7 Modelos da Programac¸a\u2dco Inteira Mixta
Apresenta-se aqui dois modelos de programac¸a\u2dco linear inteira mista. Os dados gerais do problema
sa\u2dco representados pela notac¸a\u2dcoja´ definida anteriormente, relembrando:
\u2022 N \u2032: conjunto de operac¸o\u2dces;
\u2022 pi tempo de processamento da operac¸a\u2dco i;
\u2022 M : conjunto de ma´quinas;
\u2022 A = {(i, j) : i \u2208 N \u2032, j \u2208 N \u2032, i 6= j, e i \u227a j}: conjunto de pares de operac¸o\u2dces para
representar a seque\u2c6ncia tecnolo´gica de fabricac¸a\u2dco de cada produto;
\u2022 m(i) = mi: uma func¸a\u2dco aplicada ao conjunto N
\u2032 para definir a ma´quina que execulta cada
operac¸a\u2dco;
\u2022 E = {(i, j) : i \u2208 N \u2032, j \u2208 N \u2032, i 6= j e m(i) = m(j)}: conjunto de pares de operac¸o\u2dces para
representar as operac¸o\u2dces executada em uma mesma ma´quina. Note que, se (i, j) \u2208 E,
enta\u2dco, (j, i) \u2208 E;
\u2022 M um valor positivo grande;
\u2022 nk : nu´mero de operac¸o\u2dces executadas na ma´quina mk.
1.6.7.1 Modelo de Manne
Varia´veis:
\u2022 ti a data de in´\u131cio da operac¸a\u2dco i
\u2022 yij \u2208 {0, 1}, \u2200(i, j) \u2208 E
yij =
{
1 se i precede j em mk = m(i) = m(j)
0 se j precede i em mk = m(i) = m(j);
Modelo:
minCmax
tj \u2212 ti \u2265 pi \u2200(i, j) \u2208 A
tj \u2265 ti + pi \u2212M(1\u2212 yij) \u2200 (i, j) \u2208 E
yij + yji = 1 \u2200 {(i, j); (j, i)} \u2282 E
Cmax \u2265 ti + pi \u2200 i \u2208 N
\u2032
Prof. Carlos Roberto Vena\u2c6ncio de Carvalho Novembro de 2010 - DEP EE UFMG
1.6.8 - Modelo de Wagner 60
1.6.8 Modelo de Wagner
Varia´veis
\u2022 y
(l)
i =
{
1 se i e´ a le´zima operac¸a\u2dco na ma´quina m(i)
0 se na\u2dco
\u2022 t
(l)
k : data de in´\u131cio da l
e´zima operac¸a\u2dco na ma´quina mk
\u2022 s
(l)
k : durac¸a\u2dco entre o fim da l
e´zima operac¸a\u2dco e o comec¸o da (l + 1)e´zima operac¸a\u2dco na
ma´quina mk (varia´vel de folga)
\u2022 s0k : durac¸a\u2dco entre 0 e a primeira operac¸a\u2dco na ma´quina mk
\u2022 T
(l)
k : tempo de processamento da l
e´zima operac¸a\u2dco na ma´quina mk.
Modelo:
minCmax
t
(l1)
k1
+ piy
(l1)
i \u2264 t
(l2)
k2
+M(2\u2212 y
(l1)
i \u2212 y
(l2)
j )
\u2200
\uf8f1\uf8f2
\uf8f3
(i, j) \u2208 A,
l1 = 1, . . . , nk1,
l2 = 1, . . . , nk2
T
(l)
k =
\u2211
i\u2208N \u2032:m(i)=k
piy
(l)
i \u2200 mk \u2208 M, l = 1, . . . , nk
\u2211
i\u2208N \u2032:m(i)=mk
y
(l)
i = 1 \u2200 mk \u2208M, l = 1, . . . , nk
nk\u2211
l=1
y
(l)
i = 1 \u2200 i \u2208 N
\u2032
t
(1)
k = s
0
k \u2200 k \u2208M
t
(r)
k =
l=r\u22121\u2211
l=1
(T
(l)
k + s
(l)
k ) mk \u2208 M, r = 1, . . . , nk
Cmax \u2265 t
(nk)
k + T
(nk)
k \u2200 mk \u2208M
Prof. Carlos Roberto Vena\u2c6ncio de Carvalho Novembro de 2010 - DEP EE UFMG
1.6.8 - Modelo de Wagner 61
Exemplo 1.15 Escrever o modelo de Wagner para o problema:
job oi : ma´quina (pi)
1 o1 : 1(5) o2 : 2(3) o3 : 3(4) o4 : 4(7)
2 o5 : 2(6) o6 : 1(5) o7 : 4(3) o8 : 5(4)
Prof. Carlos Roberto Vena\u2c6ncio de Carvalho Novembro de 2010 - DEP EE UFMG