RESUMEN DEL ARTICULO - PROGRAMACIÓN LINEAL

PROGRAMACION DE TRABAJOS EN UNA MAQUINA UTILIZANDO UN MODELO DE

PROGRAMACION LINEAL ENTERA

En el presente artículo se presenta una aplicación de la Programación Lineal Entera en la solución de un problema de programación de un conjunto de operaciones necesarias para la realización de dos trabajos en una sola máquina.

EL PROBLEMA

Considere el caso en el que se deben programar n trabajos en una sola máquina y cada uno de los n trabajos esta compuesto de m operaciones, con tiempos de duración pi, además cada uno de los n trabajos posee una fecha de entrega dn y tiene asociado una penalización por entrega tardía de tn por cada unidad de tiempo de retrazo. Finalmente a cada trabajo se asocia una red de precedencias que representa el orden específico de las operaciones para cada uno de ellos. La situación se muestra gráficamente en la Figura1. El objetivo del problema es determinar las fechas de inicio de cada una de las operaciones de tal manera que se genere la menor penalización total por trabajos tardíos. Es necesario tener en cuenta que como se está programando en una sola máquina, el modelo no puede permitir el traslape en el periodo de realización de dos operaciones pues el recurso solo puede realizar una al tiempo. Por otro lado es indispensable respetar las

relaciones de precedencia sobre las operaciones de cada uno de los productos, es así por ejemplo que para el producto 1 la tarea B no puede ser realizada antes de que termine la tarea A. Además las fechas de entrega de cada uno de los trabajos generan una restricción adicional al modelo.

   

Análisis de las restricciones de no traslape entre operaciones

Sea xi la fecha de inicio de la operación i, el modelo debe determinar las correspondientes a las mn tareas de tal manera que la penalización total por trabajos tardíos sea mínima. Como se observa en la Figura 2, para las tareas i y j se debe cumplir que:

Donde la relación (1) representa que la tarea i se realiza después de la tarea j y la (2) que la tarea j se realiza después de la tarea j. El modelo debe de estar en la capacidad de determinar cual de las dos alternativas anteriores debe de ser la restricción activa dejando la otra como restricción no activa. Para ello se define la variable binaria auxiliar yij que se definirá de la siguiente manera:

Donde M representa un número muy grande para las condiciones del problema. Es de importancia definir que este tipo de restricción sólo sería aplicable a aquellas operaciones que no sean tengan ninguna relación de precedencia y que por lo tanto podrían llegar a programarse simultáneamente.

Análisis de las restricciones de precedencia

Sea xi la fecha de inicio de la tarea i, se debe de cumplir para cualquier tarea j que sea precedente  de i que:

Está restricción solo debe de ser utilizada para relacionar aquellas operaciones j que son precedentes directas de alguna operación i, puesto que cualquier operación k precedente de j quedaría incluida.

Análisis de las restricciones de tiempo de entrega

Sea xi la fecha de inicio de la última operación i del trabajo o producto k, la restricción que corresponde a la fecha de entrega estaría representada por:

Donde sk representa una variable de desviación que permite modelar la diferencia entre la fecha de entrega del trabajo k y su fecha de terminación. Esta variable tiene la característica de no estar restringida en signo, pues como se observa en la Figura 3, sk ≥ 0 representaría una terminación temprana del trabajo, mientras que una sk≤ 0 representaría una terminación tardía del trabajo que generaría una multa tk por cada día de retraso.

Como la variable sk es no restringida en signo debe de ser remplazada por la resta de dos variables restringidas en signo que no pueden ser consideradas básicas de manera simultánea en cualquier solución del modelo. De acuerdo a lo anterior la variable sk deberá ser remplazada en el modelo por:

De tal manera que ska y skb ≥ 0. Debido a que estas variables son linealmente dependientes, no pueden ser simultáneamente en cualquier solución > 0. Lo que significa que solo una puede tener un valor >0, lo cual obligaría que la otra tomaría un valor de cero, pudiendo, si ocurrir que ambas sean iguales a cero. Cuando ska > 0 y skb = 0, se generaría un valor positivo para sk siendo correspondiente al caso (a) de la Figura 3, mientras que si skb > 0 y ska = 0 se obtendría un valor negativo para sk correspondiendo al caso (b) de la misma figura. Por lo tanto una expresión final para la restricción sería:

De la discusión anterior se infiere que la variable de desviación que modela los días de retrazo respecto a la fecha de entrega corresponde a skb. Por lo tanto, la función objetivo que representaría la meta de minimizar las multas por retrasos en la entrega estaría dada por:

EL CASO

Considérese la programación de trabajo en un taller que fabrica dos productos finales usando una sola máquina. Los dos trabajos usan en su realización un total de 8 operaciones, cuyas relaciones de precedencia se muestran en la Figura 4. Las Tablas 1 y 2 proporcionan los datos básicos del problema. El objetivo es determinar un plan de producción que minimice la multa total por entrega tardía de los dos productos.

Planteamiento del modelo Las variables de decisión del modelo corresponden a:

xi, Fecha de inicio de la operación i i = 1……..8

ska, Variable de desviación que representa terminación a tiempo del trabajo k. k = 1 y 2.

skb, Variable de desviación que representa terminación tardía del trabajo k. k = 1 y 2.

M1, es un número muy grande

Función Objetivo:

Una vez reordenado el modelo, por ejemplo, ubicando en el mismo lado de las desigualdades a todas las variables. Se obtuvo el siguiente modelo, que fue alimentado en el  LINDO (software especializado para la solución de modelos matemáticos de Investigación de Operaciones):

LINDO (Linear, Interactive, and Discrete Optimizer) es una herramienta computacional para resolver modelos de programación entera, lineal y cuadrática.

min 5s1b+4s2b

st

x1-x2+100y12>=7

x2-x1-100y12>=-95

x1-x3+100y13>=4

x3-x1-100y13>=-95

x1-x5+100y15>=6

x5-x1-100y15>=-95

x1-x6+100y16>=7

x6-x1-100y16>=-95

x1-x8+100y18>=8

x8-x1-100y18>=-95

x2-x3+100y23>=4

x3-x2-100y23>=-93

x2-x5+100y25>=6

x5-x2-100y25>=-93

x2-x6+100y26>=7

x6-x2-100y26>=-93

x2-x8+100y28>=8

x8-x2-100y28>=-93

x3-x4+100y34>=3

x4-x3-100y34>=-96

x3-x5+100y35>=6

x5-x3-100y35>=-96

x3-x7+100y37>=5

x7-x3-100y37>=-96

x4-x5+100y45>=6

x5-x4-100y45>=-97

x4-x6+100y46>=7

x6-x4-100y46>=-97

x4-x8+100y48>=8

x8-x4-100y48>=-97

x5-x6+100y56>7

x6-x5-100y56>=-94

x6-x7+100y67>=5

x7-x6-100y67>=-93

x7-x8+100y78>=8

x8-x7-100y78>=-95

x4-x1>=5

x4-x2>=7

x7-x4>=3

x7-x6>=6

x6-x3>=4

x8-x5>=6

x8-x6>=7

x7+s1a-s1b=8

x8+s2a-s2b=9

end

gin3 x1

gin x2

gin x3

gin x4

gin x5

gin x6

gin x7

gin x8

gin s1a

gin s1b

gin s2a

gin s2b

int y12

int y13

int y15

int y16

int y18

int y23

int y25

int y26

int y28

int y34

int y35

int y37

int y45

int y46

int y48

int y56

int y67

int4 y78

La solución obtenida es:

Según el reporte del LINDO, las fechas de inicio de cada una de las operaciones están dadas por:

CONCLUSIONES Y RECOMENDACIONES

En este artículo queda en evidencia la importancia del modelamiento matemático en la solución de problemas empresariales. En este caso se llegó rápidamente a una solución asistida por el LINDO como herramienta informática. Este problema tendría como característica principal la necesidad de evaluar 8! = 80640 alternativas diferentes para la secuenciación de las tareas necesarias para la realización de los 2 trabajos. Este gran número de diferentes formas de ordenación impone una fuerte restricción a la solución de problema por revisión exhaustiva las posibles alternativas.

El uso de variables binarias es importante para el modelamiento de situación en los que se tienen alternativas del tipo si o no, como es el caso de la elección de restricciones del tipo el uno el otro, en las que se debe seleccionar cual de ellas deberá ser efectivamente restrictiva. A través del uso de este tipo de variable fue posible modelar una condición importante del problema que radicaba en la necesidad de no permitir que dos operaciones se programaran simultáneamente.