Heurística de programación de fecha de vencimiento modificada
La heurística de programación de fecha de vencimiento modificada (MDD) es una heurística codiciosa que se utiliza para resolver el problema de tardanza ponderada total de una sola máquina (SMTWTP).
Presentación
La programación de la fecha de vencimiento modificada es una heurística de programación, creada en 1982 por Baker y Bertrand, [1] utilizada para resolver el problema de tardanza ponderada total de una sola máquina NP-hard . Este problema se centra en reducir la tardanza global de una lista de tareas que se caracterizan por su tiempo de procesamiento, fecha de vencimiento y peso al reordenarlas.
Algoritmo
Principio
Esta heurística funciona de la misma manera que otros algoritmos codiciosos. En cada iteración, busca el siguiente trabajo para programar y lo agrega a la lista. Esta operación se repite hasta que no quede ningún trabajo sin programar. MDD es similar a la heurística de la fecha de vencimiento más temprana (EDD), excepto que MDD tiene en cuenta la secuencia parcial de trabajos que ya se han construido, mientras que EDD solo mira las fechas de vencimiento de los trabajos.
Implementación
Aquí hay una implementación del algoritmo MDD en pseudocódigo. Toma una lista desordenada de tareas y devuelve la lista ordenada aumentando la fecha de vencimiento modificada:
función mdd (procesado, tarea) return max (procesado + task.processTime, task.dueDate) función mddSort (tareas) unsortedTasks = copiar (tareas) sortedTasks = lista procesado = 0 while unsortedTasks no está vacío bestTask = unsortedTasks.getFirst () bestMdd = mdd (procesado, bestTask) para tareas en tareas no ordenadas mdd = mdd (procesado, tarea) si mdd <bestMdd entonces bestMdd = mdd bestTask = tarea sortedTasks. pushBack (bestTask) unsortedTasks. eliminar (bestTask) procesado + = bestTask.processTime return sortedTasks
Ejemplo practico
En este ejemplo, programaremos salidas de vuelos. Cada vuelo se caracteriza por:
- una fecha de vencimiento: la hora después de la cual se espera que el avión despegue
- un tiempo de procesamiento: la cantidad de tiempo que tarda el avión en despegar
- un peso: un valor arbitrario para especificar la prioridad del vuelo.
Necesitamos encontrar una orden para que el vuelo despegue que resulte en la menor tardanza ponderada total. Para este ejemplo usaremos los siguientes valores:
| N ° | Fecha de vencimiento | Tiempo de procesamiento | Peso |
|---|---|---|---|
| 1 | 12 | 8 | 2 |
| 2 | 18 | 9 | 5 |
| 3 | 10 | 5 | 2 |
| 4 | 14 | 6 | 8 |
En el orden predeterminado, la tardanza ponderada total es 136.
El primer paso es calcular la fecha de vencimiento modificada para cada vuelo. Dado que la hora actual es 0 y, en nuestro ejemplo, no tenemos ningún vuelo cuya fecha de vencimiento sea menor que su tiempo de procesamiento, el mdd de cada vuelo es igual a su fecha de vencimiento:
| N ° | Fecha de vencimiento modificada |
|---|---|
| 1 | 12 |
| 2 | 18 |
| 3 | 10 |
| 4 | 14 |
A continuación, se procesa el vuelo con el MDD más pequeño (Vuelo n ° 3) y se calcula la nueva fecha de vencimiento modificada. La hora actual es ahora a las 5.
| N ° | Fecha de vencimiento | Tiempo de procesamiento | Fecha de vencimiento modificada |
|---|---|---|---|
| 3 | 10 | 5 | N / A |
| 1 | 12 | 8 | 13 |
| 2 | 18 | 9 | 18 |
| 4 | 14 | 6 | 14 |
La operación se repite hasta que no queden más vuelos sin programar.
Obtenemos los siguientes resultados:
| N ° | Fecha de vencimiento | Tiempo de procesamiento |
|---|---|---|
| 3 | 10 | 5 |
| 1 | 12 | 8 |
| 4 | 14 | 6 |
| 2 | 18 | 9 |
En este orden, la tardanza ponderada total es 92.
Este ejemplo se puede generalizar para programar cualquier lista de trabajo caracterizada por una fecha de vencimiento y un tiempo de procesamiento.
Rendimiento
La aplicación de esta heurística dará como resultado una lista ordenada de tareas cuya tardanza no se puede reducir mediante el intercambio de pares adyacentes. [2] La complejidad de MDD es .
Variaciones
Existe una versión de MDD llamada fecha de vencimiento modificada ponderada (WMDD) [3] que tiene en cuenta los pesos. En tal caso, la función de evaluación se reemplaza por:
función wmdd (procesada, tarea) return (1 / task.weight) * max (task.processTime, task.dueDate - procesada)
Referencias
- ^ Kenneth R. Baker, JWM Bertrand, Una regla de prioridad dinámica para la programación contra fechas de vencimiento , Journal of Operations Management Vol. 3, p37-42, 1982.
- ^ JC Nyirenda, Relación entre la regla de fecha de vencimiento modificada y la heurística de Wilkerson e Irwin , ORiON Vol. 17, p101-111, 2001.
- ^ John J. Kanet, Xiaoming Li, Una regla de fecha de vencimiento modificada ponderada para secuenciar para minimizar la tardanza ponderada , Journal of Scheduling N ° 7, p261-276, 2004.
Ver también
