Algoritmo de Lawler

Algoritmo para la programación de problemas

El algoritmo de Lawler es un algoritmo eficiente para resolver una variedad de problemas de programación restringida, en particular la programación de una sola máquina . ^[1] Puede manejar restricciones de precedencia entre trabajos, lo que requiere que ciertos trabajos se completen antes de que se puedan iniciar otros. Puede programar trabajos en un solo procesador de una manera que minimice la tardanza máxima , la tardanza o cualquier función de ellos.

Definiciones

Existen n puestos de trabajo. Cada puesto de trabajo se denota por y tiene las siguientes características: ${\displaystyle i}$

• Tiempo de procesamiento, denotado por p _i ;
• Tiempo debido, denotado por . ${\displaystyle d_{i}}$
• Función de costo, denotada por ; es una función débilmente creciente del tiempo en que el trabajo i completa su ejecución, denotado por . ${\displaystyle g_{i}}$ ${\displaystyle F_{i}}$

La función objetivo es . ^[2] Algunos casos especiales son: ${\displaystyle min\,max_{0\leq i\leq n}\,g_{i}(F_{i})}$

• Cuando , la función objetivo corresponde a minimizar la demora máxima ${\displaystyle g_{i}(F_{i})=F_{i}-d_{i}=L_{i}}$
• Cuando , el objetivo corresponde a minimizar la tardanza máxima . ${\displaystyle g_{i}(F_{i})=max{(F_{i}-d_{i},0)}}$

Algoritmo

El algoritmo construye el cronograma de principio a fin. Para cada paso de programación, solo analiza las tareas de las que no dependen otras tareas y coloca la que tiene la fecha de vencimiento más tardía al final de la cola de programación. Luego, repite este proceso hasta que se programen todos los trabajos.

El algoritmo funciona planificando el trabajo con el menor impacto lo más tarde posible. A partir de ahí, se inicia el tiempo de procesamiento del trabajo . ${\displaystyle t=\sum p_{j}}$ ${\displaystyle p_{j}}$ ${\displaystyle j}$

 ${\displaystyle S}$conjunto de trabajos ya programados (al inicio: S = ) conjunto de trabajos cuyos sucesores han sido programados (al inicio: todos los trabajos sin sucesores) hora en la que se completará el próximo trabajo (al inicio: ) mientras que seleccione de modo que programe de modo que se complete a las hora agregar a , eliminar de y actualizar . fin mientras ${\displaystyle \emptyset }$ ${\displaystyle J}$ ${\displaystyle t}$ ${\displaystyle t=\sum p_{j}}$ ${\displaystyle J\neq \emptyset }$  ${\displaystyle j\in J}$ ${\displaystyle f_{j}(t)=min_{k\in J}f_{k}(t)}$ ${\displaystyle j}$ ${\displaystyle t}$ ${\displaystyle j}$ ${\displaystyle S}$ ${\displaystyle j}$ ${\displaystyle J}$ ${\displaystyle J}$ ${\displaystyle t=t-p_{j}}$

Ejemplo 1

Suponiendo que hay tres trabajos: t1, t2 y t3, con las siguientes restricciones de precedencia:

• t1-> t2, t1 debe terminar antes que t2
• t1-> t3, t1 debe terminar antes que t3

Y los siguientes plazos (fecha de vencimiento en un mes)

• t1: 2do día
• t2: 5to día
• t3: día 8

Ahora construimos el conjunto de trabajos requerido:

• S = {vacío}, conjunto inicialmente vacío de trabajos programados
• J = {t2, t3}, el conjunto de trabajos cuyos sucesores han sido programados o trabajos sin sucesores. t2 y t3 no tienen sucesores.

Repita los siguientes pasos hasta que J esté vacío:

• seleccione un trabajo j en J, de modo que su fecha de vencimiento sea la más reciente, en este ejemplo es t3 con fecha de vencimiento el día 8.
• mueve j desde J al frente de S, ahora J = {t2}, S={t3}.
• Actualice J para agregar cualquier trabajo nuevo cuyos sucesores hayan sido programados. No hay ninguno en este momento.

Haz la siguiente ronda:

• Seleccione un trabajo j en J, de modo que su fecha de vencimiento sea la más reciente. Esta vez es t2 con fecha de vencimiento el día 5.
• Mueva j desde J al frente de S, ahora J = {vacío}, S={t2, t3}
• Actualice J para agregar cualquier trabajo nuevo cuyos sucesores hayan sido programados, ahora J = {t1} ya que tanto t2 como t3 han sido programados.

Haz la siguiente ronda:

• Seleccione un trabajo j en J={t1}, de modo que su fecha de vencimiento sea la más reciente. En este ejemplo, es t1.
• Mueva j desde J al frente de S, ahora J = {vacío}, S={t1, t2, t3}
• Actualizar J para agregar cualquier trabajo nuevo cuyos sucesores hayan sido programados. No hay nada que agregar.

J ahora está vacío. Fin.

Por lo tanto, el programa final es t1 -> t2 -> t3, ya que S = {t1, t2, t3}

Ejemplo 2

Un ejemplo más complejo, con pasos simplificados: Los trabajos y las restricciones de precedencia se muestran a continuación: un nodo padre --> nodo hijo en el árbol.

 j1 (2) / \ dos y tres (2) (4) / \ | J4 J5 J6(3) (5) (6) 

Las fechas de vencimiento de los trabajos se muestran debajo de cada nodo del árbol entre paréntesis.

• j1:2
• j2: 5
• j3:4
• j4:3
• j5: 5
• j6:6

Ahora mira el conjunto de trabajos sin sucesores, busca el que tenga la fecha de vencimiento más reciente y colócalo al frente de S:

• El conjunto S sería { j1, j2, j4, j3, j5, j6 }

Referencias

1. Steven Nahmias. Análisis de producción y operaciones. 2008. ISBN  978-0-07-126370-2
2. Joseph YT. Leung. Manual de programación: algoritmos, modelos y análisis de rendimiento. 2004. ISBN 978-1-58488-397-5 

Lectura adicional

• Michael Pinedo. Planificación: teoría, algoritmos y sistemas. 2008. ISBN 978-0-387-78934-7 
• Conway, Maxwell, Miller. Teoría de la programación. 1967. ISBN 0-486-42817-6