Planeación de la producción
Enviado por DIANA MILENA ALVARADO PINZON • 19 de Septiembre de 2022 • Trabajos • 410 Palabras (2 Páginas) • 92 Visitas
Problema 4
Descripción del problema:
Suponga que se tienen los siguientes trabajos que deben ser secuenciados y tienen restricciones de precedencia como se muestra en la Figura 1. Se tiene una sola máquina
[pic 1]
Realizar el ejercicio a través de un modelo de programación lineal entera mixta que minimice el retardo máximo.
Formulación matemática
Tenemos un problema en donde se nos presenta una sola máquina y 19 trabajos por procesar, tenemos restricciones de precedencia, distintas fechas de entrega, y como función objetivo tenemos minimizar el retardo máximo, con estos parámetros y sabiendo el objetivo, emplearemos un modelo de programación lineal entera mixta, basado en el algoritmo de Lawler, para obtener un valor óptimo que minimice el retardo máximo y nos entregue la secuencia de los trabajos a procesar.
Notación de Graham:
[pic 2]
Cmax | Suma de los tiempos de procesamiento |
J | Conjunto de trabajos ya programados |
[pic 3] | Complemento del conjunto J, es decir, el conjunto de trabajos que faltan por programar |
[pic 4] | Conjunto de todos los trabajos sin sucesores (Subconjunto de |
Lj | Retardo del trabajo j |
Dj | Fechas de entrega del trabajo j |
Pj | Tiempo de procesamiento del trabajo j |
i | Trabajos |
Descripción del algoritmo:
Paso 1:
[pic 6]
[pic 7]
[pic 8]
[pic 9]
Paso 2: [pic 10]
Sea tal que [pic 11]
Colocar en J en la K-ésima posición [pic 12]
Eliminar de representa el conjunto de trabajos que pueden ser programados inmediatamente antes del conjunto J [pic 13][pic 14]
Paso 3:
Si entonces el algoritmo finalizo[pic 15]
Si k = k-1, entonces ir al paso 2
Función objetivo:
[pic 16]
Variables de decisión:
[pic 17]
[pic 18]
[pic 19]
[pic 20]
Parámetros:
[pic 21]
[pic 22]
Restricciones:
[pic 23]
[pic 24]
[pic 25]
[pic 26]
[pic 27]
[pic 28]
Síntesis de Resultados
Una vez realizado el modelo de programación matemática para el conjunto de trabajos dados, y cumpliendo con cada una de las restricciones de precedencia, y con el objetivo de minimizar el retardo máximo, se logro encontrar la secuencia óptima que cumple con el objetivo para este ejercicio.
...