TALLER 2 Planeación y control de la producción

Vista previa del material en texto

UNIVERSIDAD DISTRITAL FRANCISCO JOSE DE CALDAS 
PROYECTO CURRICULAR DE INGENIERIA INDUSTRIAL 
AREA SISTEMAS PRODUCTIVO 
Código. 110 Créditos: 3. Grupo 025 
 
TALLER 2 PROGRAMACIÓN Y CONTROL DE LA PRODUCCIÓN_Gr.25 
Código Nombre % Participación en 
el trabajo / 100% 
Nota 
20171015098 Jenniffer Alejandra Benavides Liévano 33% 
20162015433 Iván Felipe Mejía Peña 33% 
20171015054 José Mauricio Lobatón Gómez 33% 
 
Problema 1 
Suponga que se tienen los siguientes trabajos que deben ser secuenciados y tienen restricciones de 
precedencia como se muestra en la figura. Se tiene una sola maquina 
 
Figurta 1.Tiempos asociados a los trabajos. 
 
Tabla.1. Tiempos de trabajo 
a) Con los datos presentados anteriormente usted debe codificar un algoritmo que solucione 
el problema de minimizar el retardo máximo. Recuerde que el algoritmo debe solucionar 
cualquier tipo instancia dependiente del tamaño de esta. Usted puede utilizar cualquier 
programa para codificar el algoritmo, pero el código debe estar debidamente comentado 
(java, phyton, c++, vba, gams, Xpress –MP) 
 
b) Formule y resuelva un modelo de programación lineal general que represente la situación 
del problema anterior, formule claramente conjuntos, parámetros, variables de decisión, 
función objetivo y restricciones 
 
Debido a la naturaleza del problema, donde el número de máquinas a emplear es uno, se tienen 
precedencias entre las máquinas, y la función objetivo es minimizar el retardo, se empleara el 
algoritmo de lawler, el cual se describe a continuación: 
 
1|𝑃𝑟𝑒𝑐𝑒𝑑𝑒𝑛𝑐𝑖𝑎|𝐿𝑗 
 
𝐶𝑚𝑎𝑥 Completar el último trabajo 
𝐽 Conjunto de trabajos ya programados 
Trabajos 
Tiempos de 
entrega 
Tiempos de 
procesamiento
n d_J p_j
1 8 15
2 4 14
3 7 15
4 5 4
5 15 13
6 12 8
7 3 16
8 7 8
9 15 12
10 6 5
11 9 14
12 17 12
13 14 16
14 5 6
15 20 4
16 14 16
17 8 8
18 16 11
19 16 3
𝐽𝐶 Complemento del conjunto J, es decir el 
conjunto de trabajos que faltan por 
programar 
 
𝐽´ 
Conjunto de todos los trabajos sin sucesores 
(Subconjunto de 
𝐽𝐶) 
𝐿𝑗 Retardo del trabajo tipo j 
𝑑𝑗 Tiempos de entrega del trabajo tipoi 
𝑃𝑗 Tiempo de procesamiento del trabajo tipo j 
𝑛 Trabajos 
 
 
Descripción del algoritmo 
Paso 1 
𝐶𝑚𝑎𝑥 = ∑ 𝑃𝑗 
𝐽 = ∅ 
𝐽𝐶 = {1,2, … 𝑛} 
𝐽´ = 𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑡𝑜𝑑𝑜𝑠 𝑙𝑜𝑠 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 sin 𝑠𝑢𝑐𝑒𝑠𝑜𝑟𝑒𝑠 
Paso 2 
𝐷𝑒𝑗𝑎𝑟 𝑞𝑢𝑒 𝐽∗𝑠𝑒𝑎 𝑡𝑎𝑙 𝑞𝑢𝑒 ℎ𝐽∗ ∑ 𝑃𝑗
𝐽∈𝐽𝐶
= min𝐽∈𝐽𝐶 ℎ𝑗 [∑ 𝑃𝑗 − 𝑑𝑗] 
𝐶𝑜𝑙𝑜𝑐𝑎𝑟 𝐽∗𝑒𝑛 𝐽 𝑒𝑛 𝑙𝑎 𝐾 − 𝑒𝑠𝑖𝑚𝑎 𝑝𝑜𝑠𝑖𝑐𝑖ó𝑛 
𝐸𝑙𝑖𝑚𝑖𝑛𝑎𝑟 𝐽∗ 𝑑𝑒 𝐽𝐶 𝑟𝑒𝑝𝑟𝑒𝑠𝑒𝑛𝑡𝑎 𝑒𝑙 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 𝑞𝑢𝑒 𝑝𝑢𝑒𝑑𝑒𝑛 𝑠𝑒𝑟 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑎𝑑𝑜𝑠 
 𝑖𝑛𝑚𝑒𝑑𝑖𝑎𝑡𝑎𝑚𝑒𝑛𝑡𝑒 𝑎𝑛𝑡𝑒𝑠 𝑑𝑒𝑙 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝐽 
Paso 3 
𝑆𝑖 𝐽𝐶 = ∅, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑝𝑎𝑟𝑒 
𝑆𝑖 𝑘 = 𝑘 − 1, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑣𝑎𝑦𝑎 𝑎𝑙 𝑝𝑎𝑠𝑜 2 
Formulación: 
Supuesto 
𝑆𝑗 = 0 
Función objetivo 
𝑀𝑖𝑛 𝐶𝑗 − 𝑑𝑗 (0) 
s.a. 
∑ 𝑌𝑗𝑘
𝑘∈𝑅𝑎𝑛𝑘
= 1 ∀𝑗 ∈ 𝐽𝑜𝑏𝑠 (1) 
∑ 𝑌𝑗𝑘
𝑗∈𝐽𝑜𝑏𝑠
= 1 ∀𝑘 ∈ 𝑅𝑎𝑛𝑘 (2) 
𝑆𝑘𝑖 + ∑ 𝑝𝑗𝑖𝑌𝑗𝑘
𝑗∈𝐽𝑜𝑏𝑠 
≤ 𝑆𝑘+1,𝑖 ∀𝑖 ∈ 𝑀𝑎𝑐ℎ, 𝑘 ∈ 𝑅𝑎𝑛𝑘 \𝑘 ≠ 𝑛 (3) 
𝑆𝑘𝑖 + ∑ 𝑝𝑗𝑖𝑌𝑗𝑘𝑗∈𝐽𝑜𝑏𝑠 ≤ 𝑆𝑘,𝑖+1 ∀𝑘 ∈ 𝑅𝑎𝑛𝑘, 𝑖 ∈ 𝑀𝑎𝑐ℎ \𝑖 ≠ 𝑚 (4) 
 𝑆𝑛𝑚 + ∑ 𝑝𝑗𝑚𝑌𝑗𝑛
𝑗∈𝐽𝑜𝑏𝑠 
≤ 𝐶𝑚𝑎𝑥 (5) 
𝑆𝑘𝑚 + ∑ 𝑝𝑗𝑚𝑌𝑗𝑘
𝑗∈𝐽𝑜𝑏𝑠 
≤ 𝐶𝑚𝑎𝑥 ∀𝑘 ∈ 𝑅𝑎𝑛𝑘 (5′) 
𝑌𝑗𝑘 ∈ {0,1} ∀𝑗 ∈ 𝐽𝑜𝑏𝑠, 𝑘 ∈ 𝑅𝑎𝑛𝑘 (6) 
𝑠𝑘𝑖 ≥ 0 ∀ 𝑘 ∈ 𝑅𝑎𝑛𝑘, 𝑖 ∈ 𝑀𝑎𝑐ℎ (7) 
 
 
 
 
 
 
 
 
 
 
EJERCICIO 2 
Suponga que cuenta con 30 trabajos que deben ser secuenciados en tres diferentes máquinas siguiendo 
la misma ruta M1-M2- M3, los tiempos de procesamiento se dan en la Tabla 2. 
 
 
Tabla. 2. Tiempos de procesamiento 
 
a) Obtenga la secuencia óptima utilizando el algoritmo de Branch and Bound propuesto por Ignall and 
Schrage. Para minimizar el Makespan. 
b) Formule y resuelva un modelo de programación lineal general que represente la situación del 
problema anterior, formule claramente conjuntos, parámetros, variables de decisión, función objetivo y 
restricciones. Considere los siguientes objetivos: 
• Minimizar el Makespan 
• Minimizar el Mean Flow Time Nota: compare sus resultados con los del Taller 1. 
 
a. Algoritmo de Branch and Bound 
 
Es un problema al cual se le debe aplicar el algoritmo de Branch and Bound propuesto por Ignall and 
Schrage. Para este problema se nos pide minimizar el Cmax o makespan. Para el desarrollo del 
algoritmo se realizo de forma manual aplicando los pasos que presenta el algoritmo, además es 
importante mencionar que para el caso cuando se presenten empates se tomara el primer trabajo con 
el valor mínimo de B. 
 
Notación de Graham 
 
𝑭𝟑 | | 𝑪𝒎𝒂𝒙 
 
 Algoritmo Branch and Bound propuesto por Ignall and Schrage 
 
𝐽𝑟:𝑆𝑒𝑐𝑢𝑒𝑛𝑐𝑖𝑎 𝑃𝑎𝑟𝑐𝑖𝑎𝑙 
𝐶𝑖(𝐽𝑟): 𝑈𝑙𝑡𝑖𝑚𝑜 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑓𝑖𝑛𝑎𝑙𝑖𝑧𝑎𝑐𝑖ó𝑛 𝑒𝑛 𝑙𝑎 𝑚𝑎𝑞𝑢𝑖𝑛𝑎 𝑖 𝑒𝑛𝑡𝑟𝑒 𝑙𝑜𝑠 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 𝑒𝑛 
𝐽𝑟 𝐶1(1) = 𝑃11 , 𝐶2(1) = 𝑃11 + 𝑃12, 𝐶3(1) = 𝑃11 + 𝑃12 + 𝑃13 
𝐿𝑖𝑚𝑖𝑡𝑒𝑠: 𝑏𝑖(𝐽𝑟) = 𝐿𝑖𝑚𝑖𝑡𝑒 𝑖𝑛𝑓𝑒𝑟𝑖𝑜𝑟 𝑑𝑒 𝑙𝑎 𝑓𝑎𝑏𝑟𝑖𝑎𝑐𝑐𝑖𝑜𝑛 𝑑𝑒 𝑙𝑎 𝑚𝑎𝑞𝑢𝑖𝑛𝑎 𝑖 
 
Actualizar 
 
 
 
 
Desarrollo del algoritmo 
Como se mencionó anteriormente el problema se solucionó de forma manual haciendo uso del programa 
Excel, es decir que se fueron aplicando cada uno de los pasos anteriormente mencionados hasta tener 
todos los trabajos secuenciados es decir en el Conjunto 𝐽𝑟. Para realizar el algoritmo se hizo uso de una 
tabla como la que se puede visualizar en la imagen x donde se reúnen cada uno de los datos necesarios 
para aplicar el algoritmo. 
 
Resultados 
Para la primera ramificación se obtuvieron los datos que se pueden visualizar en la tabla x, como se puede 
observar que el trabajo seleccionado para la primera ramificación fue el 9, aunque este trabajo se cambio 
ya que la segunda ramificación a partir del trabajo nueve los valores de Max (bi) fueron mayores al 
siguiente mínimo que se tenia en la primera ramificación que era el trabajo 12 con un Max(bi) =443 siendo 
este valor el makespan que se obtuvo al finalizar este algoritmo. Para visualizar en detalle el procedimiento 
del algoritmo y cada una de sus iteraciones se recomienda ver el anexo “Branch and Bound”. 
 
tabla x. Resultados de la primera ramificación de la aplicación del algoritmo de Ignall and Schrage. 
En la tabla y se pueden visualizar las ultimas tres ramificaciones que se obtuvieron al aplicar el algoritmo 
además se observa la secuencia final la cual nos permite obtener solución óptima al problema planteado 
de minimizar el Cmax. 
C1(Jr) C2(Jr) C3(Jr) b1(Jr) b2(Jr) b3(Jr) Max (bi)
Ci(Jr) bi(Jr) Max (bi)Partial Seq Jr
1 14 26 43 378 353 456 456 0
2 14 29 41 378 353 459 459 0
3 18 35 45 378 357 465 465 0
4 19 35 43 378 358 465 465 0
5 12 18 23 378 351 448 448 0
6 13 28 47 378 352 458 458 0
7 11 21 40 378 350 451 451 0
8 14 27 48 378 353 457 457 0
9 6 11 16 379 345 441 441 1
10 7 19 30 378 346 449 449 0
11 10 23 29 378 349 453 453 0
12 4 13 26 378 343 443 443 0
13 4 17 43 378 343 447 447 0
14 13 28 37 378 352 458 458 0
15 18 34 49 378 357 464 464 0
16 21 33 58 378 360 463 463 0
17 21 26 39 378 360 456 456 0
18 15 20 36 378 354 450 450 0
19 7 23 44 378 346 453 453 0
20 8 21 35 378 347 451 451 0
21 13 18 33 378 352 448 448 0
22 7 15 41 378 346 445 445 0
23 19 32 41 378 358 462 462 0
24 11 20 29 378 350 450 450 0
25 16 24 29 378 355 454 454 0
26 6 20 41 378 345 450 450 0
27 16 27 31 378 356 457 457 0
28 9 24 43 378 348 454 454 0
29 16 23 42 378 355 453 453 0
30 6 13 31 378 345 443 443 0
Partial Seq Jr Ci(Jr) bi(Jr) Max (bi)
 
Tabla y. Resultados de las ultimas ramificaciones de la solución del problema 
El ultimo Max (bi) que se obtuvo al solucionar el problema es de Cmax=443 con la secuencia que se 
presentaen la siguiente tabla p. 
 
Tabla p. Secuencia final del problema al lado izquierdo algoritmo de Ignall and Schrage y al lado derecho 
modelo de Jonhson modificado. 
Comparando el resultado de este algoritmo con el modelo de Jonhson modificado, se pudo establecer que 
los dos algoritmos o modelos nos proporcionaron la misma respuesta es decir que se tiene un Cmax=443. 
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 26 327 346 401 383 383 443 443
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 27 337 348 384 394 403 443 443
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 28 330 347 399 383 383 443 443
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 29 337 344 399 372 388 443 443
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 26 27 343 357 405 394 398 443 443
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 26 28 336 361 420 383 383 443 443
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 26 29 343 353 420 383 383 443 443
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 26 27 28 352 372 424 394 398 443 443
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 26 27 29 359 366 424 402 400 443 443
12 5 9 30 1 2 7 3 17 10 18 11 21 13 4 6 8 14 15 16 19 20 22 23 24 25 26 27 28 29 368 379 443 368 379 443 443
Partial Seq Jr Ci(Jr) bi(Jr) Max (bi)
Secuencia Trabajo
1 12
2 5
3 9
4 30
5 1
6 2
7 7
8 3
9 17
10 10
11 18
12 11
13 21
14 13
15 4
16 6
17 8
18 14
19 15
20 16
21 19
22 20
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
Cmax 443
Pero se puede observar que las secuencias son muy distintas es decir que el problema tiene una solución 
óptima de Cmax con distintas secuencias. 
Conclusiones 
El algoritmo de Ignall and Scharage nos puede garantizar una solución optima aunque comparando con el 
modelo de Jonhson modificado se puede establecer que el algoritmo es muy complicado de desarrollar y 
requerirá mayores cálculos para llegar a la solución óptima. 
NOTA: El desarrollo de este algoritmo se encuentra en el documento Excel anexo “TALLER2_PCP_Gr25. 
xls” ingresando en la pestaña “Branch and Bound_2” 
 
b) Formule y resuelva un modelo de programación lineal 
𝐹3 | | 𝐶𝑚𝑎𝑥 
Min 𝐶𝑚𝑎𝑥 (0) 
 
Información: 
Conjuntos: 
• Jobs: conjunto de trabajos {1, . . , 𝑛} 𝑜 {𝑗1, 𝑗2, … 𝑗𝑛} 
• Mach: conjunto de maquinas {1, . . , 𝑚} o {𝑚1, . . 𝑚𝑚} 
• Rank: conjunto de posiciones de los trabajos en la 
secuencia optima {1,2, . . , 𝑛} 
Parámetros: 
• 𝑝𝑗𝑖 =tiempo de procesamiento del trabajo 𝑗 ∈ 𝐽𝑜𝑏𝑠 en la 
maquina 𝑖 ∈ 𝑀𝑎𝑐ℎ 
Variables de decisión: 
𝑌𝑗𝑘 = {
1 
0
𝑠𝑖 𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽𝑜𝑏𝑠 𝑠𝑒 𝑎𝑠𝑖𝑔𝑛𝑎 𝑎 𝑙𝑎 𝑝𝑜𝑠𝑖𝑐𝑖ó𝑛 𝑘 ∈ 𝑅𝑎𝑛𝑘 
𝑑𝑒 𝑙𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
 
𝑆𝑘𝑖 =tiempo de inicio del trabajo en la posición 𝑘 ∈ 𝑅𝑎𝑛𝑘 en la maquina 𝑖 ∈
𝑀𝑎𝑐ℎ 
𝐶𝑚𝑎𝑥 = 𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 𝑑𝑒𝑙 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑎 
Formulación: 
Min 𝐶𝑚𝑎𝑥 (0) 
s.a. 
∑ 𝑌𝑗𝑘
𝑘∈𝑅𝑎𝑛𝑘
= 1 ∀𝑗 ∈ 𝐽𝑜𝑏𝑠 (1) 
∑ 𝑌𝑗𝑘
𝑗∈𝐽𝑜𝑏𝑠
= 1 ∀𝑘 ∈ 𝑅𝑎𝑛𝑘 (2) 
𝑆𝑘𝑖 + ∑ 𝑝𝑗𝑖𝑌𝑗𝑘
𝑗∈𝐽𝑜𝑏𝑠 
≤ 𝑆𝑘+1,𝑖 ∀𝑖 ∈ 𝑀𝑎𝑐ℎ, 𝑘 ∈ 𝑅𝑎𝑛𝑘 \𝑘 ≠ 𝑛 (3) 
𝑆𝑘𝑖 + ∑ 𝑝𝑗𝑖𝑌𝑗𝑘𝑗∈𝐽𝑜𝑏𝑠 ≤ 𝑆𝑘,𝑖+1 ∀𝑘 ∈ 𝑅𝑎𝑛𝑘, 𝑖 ∈ 𝑀𝑎𝑐ℎ \𝑖 ≠ 𝑚 (4) 
 𝑆𝑛𝑚 + ∑ 𝑝𝑗𝑚𝑌𝑗𝑛
𝑗∈𝐽𝑜𝑏𝑠 
≤ 𝐶𝑚𝑎𝑥 (5) 
𝑆𝑘𝑚 + ∑ 𝑝𝑗𝑚𝑌𝑗𝑘
𝑗∈𝐽𝑜𝑏𝑠 
≤ 𝐶𝑚𝑎𝑥 ∀𝑘 ∈ 𝑅𝑎𝑛𝑘 (5′) 
𝑌𝑗𝑘 ∈ {0,1} ∀𝑗 ∈ 𝐽𝑜𝑏𝑠, 𝑘 ∈ 𝑅𝑎𝑛𝑘 (6) 
𝑠𝑘𝑖 ≥ 0 ∀ 𝑘 ∈ 𝑅𝑎𝑛𝑘, 𝑖 ∈ 𝑀𝑎𝑐ℎ (7) 
Las restricciones (1) y (2) aseguran la factibilidad de que un trabajo se asigna únicamente a una 
posición. Las restricciones (3) aseguran la secuencia por cada máquina y la posición en la solución 
óptima. Las restricciones (4) garantizan la secuencia en el tipo Flow shop. Las restricciones (5) 
calculan el valor del makespan. Las restricción (5’) son una manera alternativa de presentar de 
forma general el makespan. Las restricciones (6) y (7) definen la naturaleza de las variables de 
decisión. La función objetivo (0) minimiza el Makespan (Cmax). 
Nombre del programa anexo en Fico Xpress: 
 
Formulación del programa: 
model FlowPTO2 
uses "mmxprs"; !gain access to the Xpress-Optimizer solver 
!sample declarations section 
declarations 
 Jobs: set of integer ! Conjunto de trabajos 
 Mach: set of integer !Conjunto de maquinas 
 Rank: set of integer !conjunto de posicion en la solucion 
 p:array(Jobs,Mach) of real ! tiempos de procesamiento 
end-declarations 
initializations from "DATA2.txt" 
 p 
end-initializations 
Rank:=Jobs 
!sample declarations section 
declarations 
 Y:array(Jobs,Rank) of mpvar ! 1 si el trabajo j?Jobs se asigna en el orden k?Rank 
 S:array(Rank,Mach) of mpvar !el tiempo de inicio del trabajo en la posicion k?Rank en la 
maquina i?Mach 
 cmax:mpvar ! representa el makespan 
 asignacion:array(Rank) of linctr 
end-declarations 
! restricciones de asignacion (1) 
forall (k in Rank) sum(j in Jobs) Y(j,k)=1 
! restricciones de asignacion (2) 
forall(j in Jobs) sum(k in Rank) Y(j,k)=1 
!Restriccion de secuencia (3) 
forall(i in Mach,k in Rank|k<>Jobs.size) do 
 S(k,i)+sum(j in Jobs)p(j,i)*Y(j,k)<=S(k+1,i) 
end-do 
 
n:=Jobs.size ! numero de trabajos 
m:=Mach.size !numeor de maquinas 
 
!Restriccion de secuencia (4) 
forall(k in Rank,i in Mach|i<>m) 
S(k,i)+sum(j in Jobs)p(j,i)*Y(j,k)<=S(k,i+1) 
!Restriccion de finalizacion (5') 
S(n,m)+sum(j in Jobs)p(j,m)*Y(j,n)<=cmax 
forall(j in Jobs,k in Rank) Y(j,k) is_binary 
forall(k in Rank,i in Mach) S(k,i)>=0 
 
minimize(cmax) 
writeln("Begin running model") 
writeln("El MAKESPAN (Cmax) es " , cmax.sol) 
forall(i in Mach) do 
writeln("el tiempo de inicio en la mach",i) 
 forall(k in Rank) do 
 writeln(" trabajo en la posicion ", k," es ", getsol(S(k,i)) ) 
 end-do 
end-do 
writeln("End running model") 
end-model 
Resultado obtenido con el modelo: 
 
 
 
 
 
 
 
B) 𝐹3| |𝑤𝑗𝐶𝑗 
F.O: Min Z = ∑𝑤𝑗𝐶𝑗 
Minimizar el Mean Flow Time 
Información: 
 
• 𝐶𝑗 = 𝑝𝐽 + 𝑠𝑗 (Variable de decisión) 
• 𝑤𝑗: 𝑝𝑒𝑠𝑜 𝑜 𝑛𝑖𝑣𝑒𝑙 𝑑𝑒 𝑖𝑛𝑝𝑜𝑟𝑡𝑎𝑛𝑐𝑖𝑎 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽 (parámetro) 
• 𝑤𝑗 =
1
𝑛
 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑝𝑟𝑜𝑏𝑙𝑒𝑚𝑎 𝑎 𝑡𝑟𝑎𝑏𝑎𝑗𝑎𝑟; 𝑛 = 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 
 
 
Adicional a la información del ítem anterior, se tiene: 
 
Formulación: 
F.O: Min Z= ∑𝑤𝑗𝐶𝑗 → 𝑀𝑖𝑛 ∑
𝑐𝑗
𝑛
 (0) 
s.a. 
∑ 𝑌𝑗𝑘
𝑘∈𝑅𝑎𝑛𝑘
= 1 ∀𝑗 ∈ 𝐽𝑜𝑏𝑠 (1) 
∑ 𝑌𝑗𝑘
𝑗∈𝐽𝑜𝑏𝑠
= 1 ∀𝑘 ∈ 𝑅𝑎𝑛𝑘 (2) 
𝑆𝑘𝑖 + ∑ 𝑝𝑗𝑖𝑌𝑗𝑘
𝑗∈𝐽𝑜𝑏𝑠 
≤ 𝑆𝑘+1,𝑖 ∀𝑖 ∈ 𝑀𝑎𝑐ℎ, 𝑘 ∈ 𝑅𝑎𝑛𝑘 \𝑘 ≠ 𝑛 (3) 
𝑆𝑘𝑖 + ∑ 𝑝𝑗𝑖𝑌𝑗𝑘𝑗∈𝐽𝑜𝑏𝑠 ≤ 𝑆𝑘,𝑖+1 ∀𝑘 ∈ 𝑅𝑎𝑛𝑘, 𝑖 ∈ 𝑀𝑎𝑐ℎ \𝑖 ≠ 𝑚 (4) 
 𝑆𝑛𝑚 + ∑ 𝑝𝑗𝑚𝑌𝑗𝑛
𝑗∈𝐽𝑜𝑏𝑠 
≤ 𝐶𝑚𝑎𝑥 (5) 
𝑆𝑘𝑚 + ∑ 𝑝𝑗𝑚𝑌𝑗𝑘
𝑗∈𝐽𝑜𝑏𝑠 
≤ 𝐶𝑚𝑎𝑥 ∀𝑘 ∈ 𝑅𝑎𝑛𝑘 (5′) 
𝑌𝑗𝑘 ∈ {0,1} ∀𝑗 ∈ 𝐽𝑜𝑏𝑠, 𝑘 ∈ 𝑅𝑎𝑛𝑘 (6) 
𝑠𝑘𝑖 ≥ 0 ∀ 𝑘 ∈ 𝑅𝑎𝑛𝑘, 𝑖 ∈ 𝑀𝑎𝑐ℎ (7) 
𝐶𝑗 = 𝑝𝐽 + 𝑠𝑗 ∀ 𝑗 ∈ 𝑱 (8) 
 
Las restricciones (1) y (2) aseguran la factibilidad de que un trabajo se asigna únicamente a una posición. 
Las restricciones (3) aseguran la secuencia por cada maquina y la posición en la solución optima. Las 
restricciones (4) garantizan la secuencia en el tipo Flow shop.Las restricciones (5) calculan el valor del 
makespan. Las restriccion (5’) son una manera alternativa de presentar de forma general el makespan. Las 
restricciones (6) y (7) definen la naturaleza de las variables de decisión. La función objetivo (0) minimiza 
el Mean Flow Time. 
 
 
 
 
 
 
 
 
EJERCICIO 3 
Suponga que se cuentan con 30 trabajos que se muestran en la Tabla 3. Estos trabajos deben ser secuenciados 
en dos máquinas y además se cuenta con una regla de asignación los cuales se muestran en la columna tres 
de la tabla:Tipo 1: Trabajos que se procesan sólo en M1. 
Tipo 2: Trabajos que se procesan sólo en M2. 
Tipo 12: Trabajos que se procesan primero en M1 y luego en M2. 
Tipo 21: Trabajos que se procesan primero en M2 y luego en M1. 
 
 
Tabla. . Tiempos de procesamiento y reglas de asignación para los trabajos del proyecto 
 
a) Formule y resuelva un modelo de programación lineal general que represente la situación del 
problema anterior, formule claramente conjuntos, parámetros, variables de decisión, función 
objetivo y restricciones. Considere los siguientes objetivos: 
• Minimizar el Makespan 
• Minimizar el Mean Flow Time 
 
b) Realice un diagrama de Gantt de las secuencias obtenidas y analice los resultados comparando 
con los resultados del Taller 1. 
 
 
A) 
 
J2| |Cmax 
 
Para: 
• Minimizar el Makespan (Cmax) 
𝑀𝑖𝑛 𝑍 = 𝐶𝑚𝑎𝑥 
 
 
𝐶𝑚𝑎𝑥 = max{ 𝑑𝑗 − 𝑇𝑗 − 𝐸𝑗 } 
 
a) 
Información 
Conjuntos: 
• 𝐽: 𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 
• 𝑀: 𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑚á𝑞𝑢𝑖𝑛𝑎𝑠 
Parámetros: 
𝑂𝑗 ∶ 𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑜𝑝𝑒𝑟𝑎𝑐𝑖𝑜𝑛𝑒𝑠 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽, 𝑦 {𝑂1
𝑗
, 𝑂2
𝑗
, … , 𝑂|𝑗|
𝑗
} 𝑒𝑠 𝑙𝑎 𝑜𝑟𝑑𝑒𝑛 
𝑑𝑒 𝑝𝑟𝑜𝑐𝑒𝑠𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑝𝑎𝑟𝑎 𝑗 ∈ 𝐽 
𝑝𝑖𝑗: 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑝𝑟𝑜𝑐𝑒𝑠𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽 𝑒𝑛 𝑙𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝑖 ∈ 𝑀 
Variables de decisión: 
𝑋𝑖𝑗: 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑖𝑛𝑖𝑐𝑖𝑜 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽 𝑒𝑛 𝑙𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝑖 ∈ 𝑀 
𝑌𝑣𝑞𝑖 = {
 1 𝑠𝑖 𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑣 ∈ 𝐽 𝑝𝑟𝑒𝑐𝑒𝑑𝑒 𝑎𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑞 ∈ 𝐽 | 𝑣 ≠ 𝑞, 𝑒𝑛 𝑚á𝑞𝑢𝑖𝑛𝑎 𝑖 ∈ 𝑀.
0 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
 
𝐶𝑚𝑎𝑥: 𝑀𝑎𝑘𝑒𝑠𝑝𝑎𝑛 𝑑𝑒 𝑙𝑎 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑑𝑒𝑙 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑎 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑐𝑖ó𝑛 
 
Formulación 
 𝑱𝟐| | 𝑪𝒎𝒂𝒙 
𝐹. 𝑂: 𝑀𝑖𝑛 𝑍 = 𝐶𝑚𝑎𝑥 (0) 
s.a: 
𝑿
𝒋,𝑶𝒓
𝒋 + 𝒑
𝒋,𝑶𝒓
𝒋
 
≤ 𝑿
𝒋,𝑶𝒓+𝟏
𝒋
 
 ∀ 𝒋 ∈ 𝑱, 𝒓 ∈ { 𝟏, … , |𝑶𝒋| − 𝟏} (1) 
𝑿𝒗𝒊 + 𝒑𝒗𝒊 ≤ 𝑿𝒒𝒊 + 𝑴 (𝟏 − 𝒀𝒗,𝒒,𝒊) ∀ 𝒊 ∈ 𝑴, ∀ 𝒗, 𝒒 ∈ 𝑱 | 𝒒 ≠ 𝒗 (2) 
𝑿𝒒𝒊 + 𝒑𝒒𝒊 ≤ 𝑿𝒗𝒊 + 𝑴 (𝒀𝒗,𝒒,𝒊) ∀ 𝒊 ∈ 𝑴, ∀𝒗, 𝒒 ∈ 𝑱 | 𝒒 ≠ 𝒗 (3) 
𝑿
𝒋,𝑶|𝒋|
𝒋 + 𝒑
𝒋,𝑶|𝒋|
𝒋 ≤ 𝑪𝒎𝒂𝒙 ∀ 𝒋 ∈ 𝑱 (4) 
𝑿𝒋𝒊 ≥ 𝟎 ∀ 𝒋 ∈ 𝑱, ∀ 𝒊 ∈ 𝑴 (5) 
𝒀𝒗𝒒𝒊 ∈ {𝟎, 𝟏} ∀ 𝒗, 𝒒 ∈ 𝑱 |𝒒 ≠ 𝒗, ∀ 𝒊 ∈ 𝑴 (6) 
 
 
Nombre del programa anexo en Fico Xpress: “P3_Cmax” 
(por restricciones con 
model JobShop 
uses "mmxprs"; !gain access to the Xpress-Optimizer solver 
 
declarations 
 !Parametros del modelo 
 J:set of integer!Conjunto de trabajos 
 M:set of string!Conjunto de maquinas 
 p:array(J,M) of real! tiempos de procesamiento 
 d:array(J) of real!pesos y fechas de entrega asociados a cada trabajo 
 O:array(J) of list of string !Conjunto de rutas de procesamiento de 
cada trabajo j 
 !Variables de decision 
 x:array(J,M) of mpvar !Tiempo de inicio del trabajo J en una maquina 
 y:array(J,J,M) of mpvar ! Representa la interferencia 
 cmax:mpvar !Tiempo de terminacion de todos los trabajos 
end-declarations 
!DATOS 
p::(1..29,["M1","M2"])[0,12,14,15,0,17,19,16,12,6,13,15,0,10,14,13,0,5,7,12,
10,0,4,9,4,0,13,0,18,0,21,12,21,5,15,0,7,0,0,13,13,0,7,8,19,13,11,0,16,8,6,
14,16,11,9,0,16,7] !se tomaron los primeros 29 trabajos por limitantes del 
software 
O::(1..29)[["M2"],["M2","M1"],["M2"],["M1","M2"],["M2","M1"],["M1","M2"],["M
2"],["M2","M1"],["M2"],["M2","M1"],["M1"],["M1","M2"],["M1"],["M1"],["M1"],["M
2","M1"],["M2","M1"],["M1"],["M1"],["M2"],["M1"],["M2","M1"],["M1","M2"],["M1
"],["M2","M1"],["M2","M1"],["M2","M1"],["M1"],["M2","M1"]] 
 
!Formulaci?n 
 
forall (j in J,i in M) do 
 create(x(j,i)) 
 x(j,i)>=0 
end-do 
forall(i in M,v in J,q in J|v<>q) do 
 create(y(v,q,i)) 
 y(v,q,i) is_binary 
end-do 
 
!Restricciones de secuencia 
forall(j in J) do 
 iter:=0 
 forall(r in O(j)|r<>getlast(O(j))) do 
 iter+=1 
 a:=getlast(gethead(O(j),iter)) 
 aa:=getlast(gethead(O(j),iter+1)) 
 x(j,a)+p(j,a)<=x(j,aa) 
 end-do 
end-do 
!Restricciones de finalizacion 
forall(j in J) do 
r:=getlast(O(j)) 
 x(j,r)+p(j,r)<=cmax 
end-do 
!Restricciones de interferencia 
MM:=300 
forall(i in M,v in J,q in J|v<>q) do 
 x(v,i)+p(v,i)<=x(q,i)+MM*(1-y(v,q,i)) 
 x(q,i)+p(q,i)<=x(v,i)+MM*y(v,q,i) 
end-do 
!Funcion objetivo 
 
fo1:=cmax 
!OPTIMIZAR la funcion objetivo 
minimize(fo1) 
writeln("Cmax= ",getobjval) 
forall(j in J) do 
 forall(i in O(j)) writeln ("maq ", i, " procesa el trabajo ",j," en el tiempo 
", x(j,i).sol) 
end-do 
end-model 
 
Resultado obtenido con el modelo: 
 
Fig.. Resultado obtenido para la optimización del Cmax en el ejercicio 3 
 
 
 
B) 
Min Z = ∑𝑤𝑗𝐶𝑗 
𝐽2| |𝑤𝑗𝐶𝑗 
 
• 𝐶𝑗 = 𝑝𝐽 + 𝑠𝑗 
• 𝑤𝑗: 𝑝𝑒𝑠𝑜 𝑜 𝑛𝑖𝑣𝑒𝑙 𝑑𝑒 𝑖𝑛𝑝𝑜𝑟𝑡𝑎𝑛𝑐𝑖𝑎 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽 (parámetro) 
• 𝑤𝑗 =
1
𝑛
 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑝𝑟𝑜𝑏𝑙𝑒𝑚𝑎 𝑎 𝑡𝑟𝑎𝑏𝑎𝑗𝑎𝑟; 𝑛 = 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 
 
 
F.O: Min Z= ∑𝑤𝑗𝐶𝑗 → 𝑀𝑖𝑛 ∑
𝑐𝑗
𝑛
 (0) 
 
s.a: 
𝑿
𝒋,𝑶𝒓
𝒋 + 𝒑
𝒋,𝑶𝒓
𝒋
 
≤ 𝑿
𝒋,𝑶𝒓+𝟏
𝒋
 
 ∀ 𝒋 ∈ 𝑱, 𝒓 ∈ { 𝟏, … , |𝑶𝒋| − 𝟏} (1) 
𝑿𝒗𝒊 + 𝒑𝒗𝒊 ≤ 𝑿𝒒𝒊 + 𝑴 (𝟏 − 𝒀𝒗,𝒒,𝒊) ∀ 𝒊 ∈ 𝑴, ∀ 𝒗, 𝒒 ∈ 𝑱 | 𝒒 ≠ 𝒗 (2) 
𝑿𝒒𝒊 + 𝒑𝒒𝒊 ≤ 𝑿𝒗𝒊 + 𝑴 (𝒀𝒗,𝒒,𝒊) ∀ 𝒊 ∈ 𝑴, ∀𝒗, 𝒒 ∈ 𝑱 | 𝒒 ≠ 𝒗 (3) 
𝑿
𝒋,𝑶|𝒋|
𝒋 + 𝒑
𝒋,𝑶|𝒋|
𝒋 ≤ 𝑪𝒎𝒂𝒙 ∀ 𝒋 ∈ 𝑱 (4) 
𝑿𝒋𝒊 ≥ 𝟎 ∀ 𝒋 ∈ 𝑱, ∀ 𝒊 ∈ 𝑴 (5) 
𝒀𝒗𝒒𝒊 ∈ {𝟎, 𝟏} ∀ 𝒗, 𝒒 ∈ 𝑱 |𝒒 ≠ 𝒗, ∀ 𝒊 ∈ 𝑴 (6) 
𝐶𝑗 = 𝑝𝐽 + 𝑠𝑗 ∀ 𝑗 ∈ 𝑱 (7) 
 
Nombre del programa anexo en Fico Xpress: “P3_MFT” 
Formulación del problema en FICO Xpress: 
Teniendo en cuenta que se utilizó el mismo modelo de base, acá se presentan algunas 
adaptaciones realizadas para obtener respuesta al objetivo que se solicitaba (Mean 
Flow Time): 
 
-Se agregó el parámetro wj relacionado directamente con el nuevo objetivo: 
 
!Para este caso wj=1/n=1/29 
wj: real !pesos y fechas de entrega asociados a cada trabajo 
 
-Se define la nueva función objetivo: 
!Funcion objetivo 
fo:=sum(j in J)wj*(x(j,r)+p(j,r)) 
!OPTIMIZAR la funcion objetivo 
minimize(fo) 
writeln("MFT= ",getobjval) 
forall(j in J) do 
 forall(i in O(j)) writeln ("maq ", i, " procesa el trabajo ",j," en el tiempo ", x(j,i).sol) 
end-do 
end-model 
 
 
Resultado Obtenido mediante el modelo: 
 
Fig.. Resultado obtenido para la minimización de FMT en el ejercicio 3 
 
 
 
 
 
 
EJERCICIO 4: 
Una empresa manufacturera recibe 5 órdenes de trabajo que deben ser procesados en sus instalaciones. La 
secuencia de proceso se da en la tabla 4; los tiempos de elaboración estándar por producto 𝑝𝑖𝑗 se muestran 
en la tabla 5 en horas por trabajo. Las fechas de entrega se dan en la tabla 6, suponga que se trabajan 3 
turnos por día, de lunes a domingo. Por condiciones logísticas del cliente el recibe en ciertos días a partir 
de hoy, y puede recibir a cierta hora del día (tercera columna de la tabla 6), por ejemplo para el trabajo 5 
se debe entregar en 4 días a las 18 horas (6 pm). 
Determine la secuencia óptima de operaciones en la empresa bajos las siguientes situaciones: 
• Minimizar el Makespan 
• Minimizar el Mean Flow Time 
• Minimizar las desviaciones respectoa la fecha de entrega, suponga el costo de anticipación es de 
2$/hora, y de entrega tardía de 5$/hora 
• Minimizar la máxima demora 
• Minimizar la máxima anticipación 
 
Su solución debe presentar claramente: 
• Formulación general de los modelos. 
• Diagrama de Gantt de las secuencias para cada situación. 
• Resumen de resultados de cada situación. 
• Comparación de resultados y conclusiones. 
 
 
Tabla.3 . Ruta de procesamiento 
 
 
Tabla.4 . Tiempos de procesamiento 
 
Tabla.5. Fechas de entrega 
Formulación general de los modelos. 
A) J7| |Cmax 
Para: 
• Minimizar el Makespan (Cmax) 
𝑀𝑖𝑛 𝑍 = 𝐶𝑚𝑎𝑥 
Información 
Conjuntos: 
• 𝐽: 𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 
• 𝑀: 𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑚á𝑞𝑢𝑖𝑛𝑎𝑠 
Parámetros: 
𝑂𝑗 ∶ 𝐶𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑑𝑒 𝑜𝑝𝑒𝑟𝑎𝑐𝑖𝑜𝑛𝑒𝑠 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽, 𝑦 {𝑂1
𝑗
, 𝑂2
𝑗
, … , 𝑂|𝑗|
𝑗
} 𝑒𝑠 𝑙𝑎 𝑜𝑟𝑑𝑒𝑛 
𝑑𝑒 𝑝𝑟𝑜𝑐𝑒𝑠𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑝𝑎𝑟𝑎 𝑗 ∈ 𝐽 
𝑝𝑖𝑗: 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑝𝑟𝑜𝑐𝑒𝑠𝑎𝑚𝑖𝑒𝑛𝑡𝑜 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽 𝑒𝑛 𝑙𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝑖 ∈ 𝑀 
𝑑𝑗: 𝑑𝑢𝑒 𝑑𝑎𝑡𝑒 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽𝑜𝑏𝑠 
𝑠𝑗: 𝑓𝑒𝑐ℎ𝑎 𝑑𝑒 𝑖𝑛𝑖𝑐𝑖𝑜 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽𝑜𝑏𝑠 
𝑐𝑗: 𝑓𝑒𝑐ℎ𝑎 𝑑𝑒 𝑒𝑛𝑡𝑟𝑒𝑔𝑎 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽𝑜𝑏𝑠 
 
Variables de decisión: 
𝑋𝑖𝑗: 𝑡𝑖𝑒𝑚𝑝𝑜 𝑑𝑒 𝑖𝑛𝑖𝑐𝑖𝑜 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽 𝑒𝑛 𝑙𝑎 𝑚á𝑞𝑢𝑖𝑛𝑎 𝑖 ∈ 𝑀 
𝑌𝑣𝑞𝑖 = {
 1 𝑠𝑖 𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑣 ∈ 𝐽 𝑝𝑟𝑒𝑐𝑒𝑑𝑒 𝑎𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑞 ∈ 𝐽 | 𝑣 ≠ 𝑞, 𝑒𝑛 𝑚á𝑞𝑢𝑖𝑛𝑎 𝑖 ∈ 𝑀.
0 𝑒𝑛 𝑜𝑡𝑟𝑜 𝑐𝑎𝑠𝑜
 
𝐶𝑚𝑎𝑥: 𝑀𝑎𝑘𝑒𝑠𝑝𝑎𝑛 𝑑𝑒 𝑙𝑎 𝑠𝑜𝑙𝑢𝑐𝑖ó𝑛 𝑑𝑒𝑙 𝑝𝑟𝑜𝑔𝑟𝑎𝑚𝑎 𝑑𝑒 𝑝𝑟𝑜𝑑𝑢𝑐𝑐𝑖ó𝑛 
𝑇𝑗: 𝑡𝑎𝑟𝑑𝑎𝑛𝑧𝑎 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽𝑜𝑏𝑠 
𝐸𝑗: 𝑎𝑛𝑡𝑖𝑐𝑖𝑝𝑎𝑐𝑖ó𝑛 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽𝑜𝑏𝑠 
 
𝐶𝑚𝑎𝑥 = max (𝑑𝑗 + 𝑇𝑗 − 𝐸𝑗) 
𝑇𝑗 = max (𝑐𝑗 − 𝑑𝑗; 0) 
𝐸𝑗 = max (𝑑𝑗 − 𝑐𝑗; 0) 
 
Formulación 
 𝑱𝟐| | 𝑪𝒎𝒂𝒙 
𝐹. 𝑂: 𝑀𝑖𝑛 𝑍 = 𝐶𝑚𝑎𝑥 (0) 
s.a: 
𝑿
𝒋,𝑶𝒓
𝒋 + 𝒑
𝒋,𝑶𝒓
𝒋
 
≤ 𝑿
𝒋,𝑶𝒓+𝟏
𝒋
 
 ∀ 𝒋 ∈ 𝑱, 𝒓 ∈ { 𝟏, … , |𝑶𝒋| − 𝟏} (1) 
𝑿𝒗𝒊 + 𝒑𝒗𝒊 ≤ 𝑿𝒒𝒊 + 𝑴 (𝟏 − 𝒀𝒗,𝒒,𝒊) ∀ 𝒊 ∈ 𝑴, ∀ 𝒗, 𝒒 ∈ 𝑱 | 𝒒 ≠ 𝒗 (2) 
𝑿𝒒𝒊 + 𝒑𝒒𝒊 ≤ 𝑿𝒗𝒊 + 𝑴 (𝒀𝒗,𝒒,𝒊) ∀ 𝒊 ∈ 𝑴, ∀𝒗, 𝒒 ∈ 𝑱 | 𝒒 ≠ 𝒗 (3) 
𝑿
𝒋,𝑶|𝒋|
𝒋 + 𝒑
𝒋,𝑶|𝒋|
𝒋 ≤ 𝑪𝒎𝒂𝒙 ∀ 𝒋 ∈ 𝑱 (4) 
𝑿𝒋𝒊 ≥ 𝟎 ∀ 𝒋 ∈ 𝑱, ∀ 𝒊 ∈ 𝑴 (5) 
𝒀𝒗𝒒𝒊 ∈ {𝟎, 𝟏} ∀ 𝒗, 𝒒 ∈ 𝑱 |𝒒 ≠ 𝒗, ∀ 𝒊 ∈ 𝑴 (6) 
 
Nombre del programa anexo en Fico Xpress: “P4_1Cmax” 
 
Formulación del problema en FICO Xpress: 
 
model JobShop 
uses "mmxprs"; !gain access to the Xpress-Optimizer solver 
declarations 
 !Parametros del modelo 
 J:set of integer!Conjunto de trabajos 
 M:set of string!Conjunto de maquinas 
 p:array(J,M) of real! tiempos de procesamiento 
 d:array(J) of real !pesos y fechas de entrega asociados a cada trabajo 
 O:array(J)of list of string !Conjunto de rutas de procesamiento de cada trabajo j 
 !Variables de decision 
 x:array(J,M) of mpvar !Tiempo de inicio del trabajo J en una maquina I 
 c:array(J) of mpvar !Tiempo de finalizacion de un trabajo J 
 y:array(J,J,M) of mpvar ! Representa la interferencia 
 wj:real 
 cmax:mpvar !Tiempo de terminacion de todos los trabajos 
end-declarations 
!DATOS 
p::(1..5,["M1","M2","M3","M4","M5","M6","M7"])[12,8,0,18,7,12,12,16,11,6,0,14,9,6,3,0,12,14,8,14,14,15,1
3,0,8,9,15,16,10,15,19,6,13,0,11] !tiempos de procesamiento de cada trabajo j en la máquina i 
O::(1..5)[["M1","M2","M4","M5","M6","M7"],["M6","M3","M5","M7","M2","M1"],["M3","M7","M6","M1","M5","M
4"],["M5","M2","M7","M4","M1","M6"],["M7","M1","M5","M3","M4","M2"]] ¡secuencias de máquinas para 
cada trabajo 
wj:=1/5 !supuesto del problema para pesos iguales para todos los trabajos 
d::(1..5)[54,78,54,85,90] 
!Formulación 
forall(j in J) create(c(j)) 
forall (j in J,i in M) do 
 create(x(j,i)) 
 x(j,i)>=0 
end-do 
forall(i in M,v in J,q in J|v<>q) do 
 create(y(v,q,i)) 
 y(v,q,i) is_binary 
end-do 
!Restricciones de secuencia 
forall(j in J) do 
 iter:=0 
 forall(r in O(j)|r<>getlast(O(j))) do 
 iter+=1 
 a:=getlast(gethead(O(j),iter)) 
 aa:=getlast(gethead(O(j),iter+1)) 
 x(j,a)+p(j,a)<=x(j,aa) 
 end-do 
end-do 
!Restricciones de finalizacion 
forall(j in J) do 
 r:=getlast(O(j)) 
 x(j,r)+p(j,r)=c(j) 
 c(j)<=cmax 
end-do 
!Restricciones de interferencia 
MM:=100 
forall(i in M,v in J,q in J|v<>q) do 
 x(v,i)+p(v,i)<=x(q,i)+MM*(1-y(v,q,i)) 
 x(q,i)+p(q,i)<=x(v,i)+MM*y(v,q,i) 
end-do 
!Funcion objetivo 
 fo1:=cmax 
 fo:=sum(j in J)wj*c(j) 
!OPTIMIZAR la funcion objetivo 
minimize(fo1) 
writeln("MFT= ",getact(fo)) 
writeln("Cmax= ",cmax.sol) 
forall(j in J) do 
 forall(i in O(j)) writeln ("maq ", i, " procesa el trabajo ",j," en el tiempo ", x(j,i).sol) 
end-do 
end-model 
 
 
Resultado Obtenido mediante el modelo: 
 
 
 
Fig.. Resultado obtenido para la optimización del Cmax en el ejercicio 4 
NOTA: En los anexos se encontrará el Diagrama de Gantt para este ejercicio como: PROBLEMA 
4_ITEM A (P4_1Cmax) 
 
 
 
 
B) 𝐽2| |𝑤𝑗𝐶𝑗 
Min Z = ∑𝑤𝑗𝐶𝑗 
 
• 𝐶𝑗 = 𝑝𝐽 + 𝑠𝑗 
• 𝑤𝑗: 𝑝𝑒𝑠𝑜 𝑜 𝑛𝑖𝑣𝑒𝑙 𝑑𝑒 𝑖𝑛𝑝𝑜𝑟𝑡𝑎𝑛𝑐𝑖𝑎 𝑑𝑒𝑙 𝑡𝑟𝑎𝑏𝑎𝑗𝑜 𝑗 ∈ 𝐽 (parámetro) 
• 𝑤𝑗 =
1
𝑛
 𝑝𝑎𝑟𝑎 𝑒𝑙 𝑝𝑟𝑜𝑏𝑙𝑒𝑚𝑎 𝑎 𝑡𝑟𝑎𝑏𝑎𝑗𝑎𝑟; 𝑛 = 𝑛ú𝑚𝑒𝑟𝑜 𝑑𝑒 𝑡𝑟𝑎𝑏𝑎𝑗𝑜𝑠 
 
 
F.O: Min Z= ∑𝑤𝑗𝐶𝑗 → 𝑀𝑖𝑛 ∑
𝑐𝑗
𝑛
 (0) 
 
s.a: 
𝑿
𝒋,𝑶𝒓
𝒋 + 𝒑
𝒋,𝑶𝒓
𝒋
 
≤ 𝑿
𝒋,𝑶𝒓+𝟏
𝒋
 
 ∀ 𝒋 ∈ 𝑱, 𝒓 ∈ { 𝟏, … , |𝑶𝒋| − 𝟏} (1) 
𝑿𝒗𝒊 + 𝒑𝒗𝒊 ≤ 𝑿𝒒𝒊 + 𝑴 (𝟏 − 𝒀𝒗,𝒒,𝒊) ∀ 𝒊 ∈ 𝑴, ∀ 𝒗, 𝒒 ∈ 𝑱 | 𝒒 ≠ 𝒗 (2) 
𝑿𝒒𝒊 + 𝒑𝒒𝒊 ≤ 𝑿𝒗𝒊 + 𝑴 (𝒀𝒗,𝒒,𝒊) ∀ 𝒊 ∈ 𝑴, ∀𝒗, 𝒒 ∈ 𝑱 | 𝒒 ≠ 𝒗 (3) 
𝑿
𝒋,𝑶|𝒋|
𝒋 + 𝒑
𝒋,𝑶|𝒋|
𝒋 ≤ 𝑪𝒎𝒂𝒙 ∀ 𝒋 ∈ 𝑱 (4) 
𝑿𝒋𝒊 ≥ 𝟎 ∀ 𝒋 ∈ 𝑱, ∀ 𝒊 ∈ 𝑴 (5) 
𝒀𝒗𝒒𝒊 ∈ {𝟎, 𝟏} ∀ 𝒗, 𝒒 ∈ 𝑱 |𝒒 ≠ 𝒗, ∀ 𝒊 ∈ 𝑴 (6) 
𝐶𝑗 = 𝑝𝐽 + 𝑠𝑗 ∀ 𝑗 ∈ 𝑱 (7) 
 
Nombre del programa anexo en Fico Xpress: “P4_2MFT” 
 
 
Formulación del problema en FICO Xpress: 
 
Teniendo en cuenta que se utilizó el mismo modelo de base, acá se presentan algunas 
adaptaciones realizadas para obtener respuesta al objetivo que se solicitaba (Mean 
Flow Time): 
 
-Se establece el nuevo objetivo para el programa: 
 
fo:=sum(j in J)w(j)*c(j) 
!OPTIMIZAR la funcion objetivo 
minimize(fo) 
writeln("MFT= ",fo.sol) 
writeln("Cmax= ",f.sol) 
forall(j in J) do 
 forall(i in O(j)) writeln ("maq ", i, " procesa el trabajo ",j," en el tiempo ", x(j,i).sol) 
end-do 
end-model 
Resultado Obtenido mediante el modelo: 
 
 
Fig.. Resultado obtenido para la optimización del Mean Flow Time en el ejercicio 4 
NOTA: En los anexos se encontrará el Diagrama de Gantt para este ejercicio como: PROBLEMA 
4_ITEM B(P4_2FMT): Mean Flow Time 
 
 
 
C. 
 𝑊𝐸𝑗 = $2/ℎ 
𝑊𝑇𝑗 = $5/ℎ 
𝐹. 𝑂: 𝑀𝐼𝑁 𝑍 = 2 ∗ ∑ 𝐸𝑗 +
𝑛
𝑗∈𝑗𝑜𝑏𝑠
5 ∗ ∑ 𝑇𝑗
𝑛
𝑗∈𝑗𝑜𝑏𝑠
 
 
Nombre del programa anexo en Fico Xpress: “P4_3DESV” 
Formulación del problema en FICO Xpress: 
 
Teniendo en cuenta que se utilizó el mismo modelo de base, acá se presentan algunas 
adaptaciones realizadaspara obtener respuesta al objetivo que se solicitaba (Mean 
Flow Time): 
 
-Se incluyen las nuevas variables necesarias para la optimización del nuevo objetivo: 
 
E,T:array(J)of mpvar !Tardanza y anticipación del trabajo j \in J 
 
-Se inicializan las nuevas variables: 
 
forall(j in J) create(c(j)) 
forall(j in J) do 
 create(E(j)) 
 E(j)>=0 
end-do 
forall(j in J) do 
 create(T(j)) 
 T(j)>=0 
end-do 
 
-Se establecen restricciones para las variables incluidas en este subproblema: 
 
forall(j in J)do 
c(j)-d(j)<=E(j) 
d(j)-c(j)<=T(j) 
end-do 
 
-Se establece el nuevo objetivo para el programa: 
 
!Función objetivo 
 
fo:=sum(j in J)2*E(j)+sum(j in J)5*T(j) 
 
¡OPTIMIZAR la función objetivo 
 
minimize(fo) 
writeln("El Cmax para el cual se minim. las desv. es= ",cmax.sol) 
writeln("con un costo por la desviacion de $",fo.sol) 
forall(j in J) do 
 forall(i in O(j)) writeln ("maq ", i, " procesa el trabajo ",j," en el tiempo ", x(j,i).sol) 
end-do 
end-model 
 
Resultado Obtenido mediante el modelo: 
 
Fig.. Resultado obtenido para la minimización de las desviaciones con respecto a fecha de entrega 
en el ejercicio 4. 
NOTA: En los anexos se encontrará el Diagrama de Gantt para este ejercicio como: PROBLEMA 
4_ITEM C(P4_P4_3DESV): Minimización de Desviaciones respecto a fecha de entrega. 
 
D. 𝐽2| |𝐿𝑚𝑎𝑥 
 
𝐿𝑚𝑎𝑥 = max {𝐶𝑗 − 𝑑𝑗 , 0} 
𝑀𝑖𝑛 𝐿𝑚𝑎𝑥 
Nombre del programa anexo en Fico Xpress: “P4_4Lmax” 
 
Formulación del problema en FICO Xpress: 
 
Teniendo en cuenta que se utilizó el mismo modelo de base, acá se presentan algunas 
adaptaciones realizadas para obtener respuesta al objetivo que se solicitaba (Mean Flow 
Time): 
 
-Al modelo del item C se le incluye una nueva variable de decisión: 
 
Lmax:mpvar ! Máximo retardo/demora 
… 
-Se define el Lmax dentro del modelo: 
 
forall(j in J) do 
E(j)-T(j)<=Lmax 
end-do 
 
-Se establece el nuevo objetivo a optimizar por medio del modelo: 
 
!Funcion objetivo 
 
fo:= Lmax 
 
!OPTIMIZAR la funcion objetivo 
minimize(fo) 
writeln("El Cmax para el cual se minim Lmax es ",cmax.sol) 
writeln("con un Lmax de ",fo.sol) 
 
forall(j in J) do 
 forall(i in O(j)) writeln ("maq ", i, " procesa el trabajo ",j," en el tiempo ", x(j,i).sol) 
end-do 
end-model 
Resultado Obtenido mediante el modelo: 
 
Fig.. Resultado obtenido para la minimización del Lmax en el ejercicio 4 
 
NOTA: En los anexos se encontrará el Diagrama de Gantt para este ejercicio como: PROBLEMA 
4_ITEM D (P4_4LMAX): Minimizar la máxima demora 
 
 
 
E. 𝐽2| |𝐸𝑚𝑎𝑥 
 
𝑀𝑖𝑛 𝐸𝑚𝑎𝑥 
𝑇𝑗 = max (𝑐𝑗 − 𝑑𝑗; 0) 
𝐸𝑗 = max(𝑑𝑗 − 𝑐𝑗; 0) 
 
Nombre del programa anexo en Fico Xpress: “P4_5Emax” 
Formulación del problema en FICO Xpress: 
 
Teniendo en cuenta que se utilizó el mismo modelo de base, acá se presentan 
algunas adaptaciones realizadas para obtener respuesta al objetivo que se solicitaba 
(Mean Flow Time): 
-Al modelo anterior se la agrega una nueva variable de decisión: 
Emax:mpvar !maxima anticipación 
 
-Se define el Emax dentro del modelo: 
forall(j in J)do 
c(j)-d(j)<=E(j) 
d(j)-c(j)<=T(j) 
E(j)<=Emax 
end-do 
--Se establece el nuevo objetivo a optimizar por medio del modelo: 
 
!Funcion objetivo2 
fo:= Emax 
 
!OPTIMIZAR la funcion objetivo 
minimize(fo) 
writeln("El Cmax para el cual se minim Lmax es ",cmax.sol) 
writeln("con un Emax de ",fo.sol) 
 
forall(j in J) do 
 forall(i in O(j)) writeln ("maq ", i, " procesa el trabajo ",j," en el tiempo ", x(j,i).sol) 
end-do 
 
end-model 
 
Resultado Obtenido mediante el modelo: 
 
 
Fig.. Resultado obtenido para la minimización de Emax en el ejercicio 4 
NOTA: En los anexos se encontrará el Diagrama de Gantt para este ejercicio como: PROBLEMA 
4_ITEM E(P4_5Emax):Minimizar la máxima anticipación 
 
Análisis y conclusiones (problema 4) 
Dependerá del objetivo que se persiga al aplicar determinado modelo a un plan de producción en un sistema 
Job Shop, ya que es posible obtener una solución óptima para cada caso, y mientras que algunas medidas 
de desempeño mejoran mediante un modelo, otras también empeorarán; por ejemplo en el caso de minimizar 
la máxima demora, ésta efectivamente se reduce a cero, mientras que el Makespan se incrementa bastante, 
siendo en este caso donde tiene mayor valor comparado con los demás modelos aplicados en este problema. 
BIBLIOGRAFÍA 
Ignall, E., & Schrage, L. (1965). Application of the Branch and Bound Technique to Some Flow-Shop Scheduling 
Problems. Operations Research, 13(3), 400-412. Retrieved May 14, 2021, from 
http://www.jstor.org/stable/167804 
FICO® Xpress Solver (n.d.). Xpress-Optimizer reference manual. Retrieved May 14, 2021, from 
https://examples.xpress.fico.com/resources/Xpress_Workbench/2.1/optimizer.pdf 
FICO® Xpress Solver (n.d.). FICO Xpress Optimization Examples Repository: Browser Retrieved May 14, 
2021, from https://examples.xpress.fico.com/example.pl 
 
 
 
 
 
 
ANEXOS 
(modelos en el software seleccionado, salidas y toda la información de soporte que sustente el trabajo): 
P3_Cmax (desarrollo ítem A problema 3) 
P3_MFT (desarrollo ítem B problema 3) 
P4_1Cmax (desarrollo ítem A problema 4) 
P4_2MFT (desarrollo ítem B problema 4) 
P4_3DESV (desarrollo ítem C problema 4) 
P4_4Lmax (desarrollo ítem D problema 4) 
P4_5Emax (desarrollo ítem E problema 4) 
Documento Excel con Diagramas de Gantt realizados y modelación de algunos ejercicios 
“TALLER2_PCP_Gr25” 
 
 
https://examples.xpress.fico.com/example.pl