Planeación de la producción

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]

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.  

...