El algoritmo de Lawler

El algoritmo de Lawler es un algoritmo eficiente para resolver diversos problemas de planificación con restricciones, en particular la planificación en una sola máquina . ^{[ 1 ]} Puede manejar restricciones de precedencia entre trabajos, requiriendo que ciertos trabajos se completen antes de que otros puedan comenzar. Puede planificar trabajos en un solo procesador de manera que se minimice el retraso máximo , la demora o cualquier función de estos.

Hay n trabajos. Cada trabajo se denota por${\displaystyle i}$y tiene las siguientes características:

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

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

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

El algoritmo construye la programación de atrás hacia adelante. En cada paso de la programación, solo considera las tareas de las que no dependen otras y coloca la que tiene la fecha de vencimiento más tardía al final de la cola. Luego, repite este proceso hasta que todas las tareas estén programadas.

El algoritmo funciona planificando el trabajo con el menor impacto posible lo más tarde posible. Comenzando en${\displaystyle t=\sum p_{j}}$eso ${\displaystyle p_{j}}$es el tiempo de procesamiento del trabajo${\displaystyle j}$.

${\displaystyle S}$conjunto de trabajos ya programados (al inicio: S =${\displaystyle \emptyset }$) ${\displaystyle J}$Conjunto de trabajos cuyos sucesores han sido programados (al inicio: todos los trabajos sin sucesores) ${\displaystyle t}$hora en que se completará el próximo trabajo (al inicio:${\displaystyle t=\sum p_{j}}$) mientras${\displaystyle J\neq \emptyset }$seleccionar ​${\displaystyle j\in J}$de tal manera que${\displaystyle f_{j}(t)=min_{k\in J}f_{k}(t)}$ cronograma${\displaystyle j}$de tal manera que se complete en el tiempo${\displaystyle t}$ agregar${\displaystyle j}$a${\displaystyle S}$, borrar${\displaystyle j}$de${\displaystyle J}$y actualización${\displaystyle J}$. ${\displaystyle t=t-p_{j}}$fin mientras

Suponiendo que existen 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: 2º día
• t2: 5to día
• t3: octavo día

Ahora construimos el conjunto de trabajos necesarios:

• 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 tardía; en este ejemplo, es t3 con una fecha de vencimiento el 8.
• Mueve j de J al frente de S, ahora J = {t2}, S = {t3}.
• Actualiza J para añadir cualquier nuevo trabajo cuyos sucesores hayan sido programados. Esta vez no hay ninguno.

Haz la siguiente ronda:

• Seleccione un trabajo j en J, de modo que su fecha de vencimiento sea la más tardía. Esta vez es t2 con fecha de vencimiento el 5.
• mover j de J al frente de S, ahora J = {vacío}, S = {t2, t3}
• Actualizar 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 tardía. En este ejemplo, es t1.
• mover j de J al frente de S, ahora J = {vacío}, S = {t1, t2, t3}
• Actualizar J para agregar cualquier nuevo trabajo cuyos sucesores hayan sido programados. Nada que agregar.

J ahora está vacío. Fin.

Por lo tanto, el cronograma final es t1 -> t2 -> t3 como S = {t1, t2, t3}

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) / \ j2 j3 (2) (4) / \ | j4 j5 j6 (3) (5) (6) 

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

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

Ahora mira el conjunto de trabajos sin sucesores, encuentra el que tenga la fecha de vencimiento más tardía y colócalo al principio de S:

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

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