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).
La programación de 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 total ponderada 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 reordenándolas.
Esta heurística funciona de la misma manera que otros algoritmos voraces. En cada iteración, encuentra el siguiente trabajo para programar y lo agrega a la lista. Esta operación se repite hasta que no queden trabajos sin programar. MDD es similar a la heurística de 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 tiene en cuenta las fechas de vencimiento de los trabajos.
A continuación se muestra una implementación del algoritmo MDD en pseudocódigo. Toma una lista de tareas sin clasificar y devuelve la lista ordenada por fecha de vencimiento de modificación creciente:
función mdd(procesado, tarea) devuelve max(procesado + tarea.processTime, tarea.dueDate) función mddSort(tareas) tareas_sin_ordenar = copiar(tareas) sortedTasks = lista procesado = 0 mientras unsortedTasks no esté vacío mejorTarea = tareassinordenar.getFirst() bestMdd = mdd(procesado, mejorTarea) para la tarea en tareas no ordenadas mdd = mdd(procesado, tarea) Si mdd < bestMdd entonces mejorMdd = mdd bestTask = tarea sortedTasks.pushBack (mejor tarea ) tareas no ordenadas.eliminar (mejor tarea ) procesado += mejorTarea.tiempoDeProceso devolver tareas ordenadas
En este ejemplo programaremos las salidas de los vuelos. Cada vuelo se caracteriza por:
Necesitamos encontrar un orden para el despegue del vuelo que dé como resultado el menor retraso ponderado total. Para este ejemplo, utilizaremos los siguientes valores:
En el orden predeterminado, el retraso ponderado total es 136.
El primer paso es calcular la fecha de vencimiento modificada para cada vuelo. Como 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:
A continuación se procesa el vuelo con el MDD más bajo (vuelo n° 3) y se calcula la nueva fecha de vencimiento modificada. La hora actual es ahora 5.
La operación se repite hasta que no queden más vuelos sin programar.
Obtenemos los siguientes resultados:
En este orden el total de tardanzas ponderadas es 92.
Este ejemplo se puede generalizar para programar cualquier lista de trabajos caracterizados por una fecha de vencimiento y un tiempo de procesamiento.
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 .
Existe una versión de MDD denominada 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(procesado, tarea) devuelve (1 / tarea.peso) * máx. (tarea.tiempoDeProceso, tarea.FechaDeDuelo - procesado)
