Измененная эвристика планирования сроков выполнения

Эвристика планирования модифицированного срока выполнения (MDD) — это жадная эвристика, используемая для решения проблемы общего взвешенного опоздания для одной машины (SMTWTP).

Презентация

Модифицированное планирование сроков выполнения — это эвристика планирования, разработанная в 1982 году Бейкером и Бертраном. ^[1] используется для решения NP-трудной задачи об опоздании одной машины с общим взвешиванием. Эта проблема сосредоточена на уменьшении глобальной задержки списка задач, которые характеризуются временем обработки, сроком выполнения и весом, путем их изменения порядка.

Алгоритм

Принцип

Эта эвристика работает так же, как и другие жадные алгоритмы. На каждой итерации он находит следующее задание для планирования и добавляет его в список. Эта операция повторяется до тех пор, пока не останется незапланированных заданий. MDD аналогичен эвристике самого раннего срока выполнения (EDD), за исключением того, что MDD учитывает частичную последовательность уже созданных заданий, тогда как EDD учитывает только сроки выполнения заданий.

Выполнение

Вот реализация алгоритма MDD в псевдокоде. Он принимает несортированный список задач и возвращает список, отсортированный по увеличению измененного срока выполнения:

function mdd(processed, task)
    return max(processed + task.processTime, task.dueDate)
  
function mddSort(tasks)
    unsortedTasks = copy(tasks)
    sortedTasks = list
    processed = 0
    while unsortedTasks is not empty
        bestTask = unsortedTasks.getFirst()
        bestMdd = mdd(processed, bestTask)
        for task in unsortedTasks
            mdd = mdd(processed, task)
            if mdd < bestMdd then
                bestMdd = mdd
                bestTask = task
        sortedTasks.pushBack(bestTask)
        unsortedTasks.remove(bestTask)
        processed += bestTask.processTime
    return sortedTasks

Практический пример

В этом примере мы запланируем вылеты рейсов. Каждый полет характеризуется:

Срок выполнения: время, после которого самолет должен взлететь.
время обработки: количество времени, необходимое самолету для взлета.
вес: произвольное значение, определяющее приоритет полета.

Нам нужно найти команду на вылет, которая приведет к наименьшему общему взвешенному опозданию. В этом примере мы будем использовать следующие значения:

Расписание рейсов
№	Две даты	Время обработки	Масса
1	12	8	2
2	18	9	5
3	10	5	2
4	14	6	8

В порядке по умолчанию общее взвешенное опоздание равно 136.

Первым шагом является вычисление измененной даты выполнения для каждого рейса. Поскольку текущее время равно 0 и в нашем примере у нас нет ни одного рейса, срок выполнения которого меньше времени его обработки, mdd каждого рейса равен его сроку выполнения:

№	Измененная дата сдачи
1	12
2	18
3	10
4	14

Затем обрабатывается рейс с наименьшим MDD (рейс № 3) и вычисляется новый измененный срок выполнения. Текущее время сейчас 5.

№	Две даты	Время обработки	Измененная дата сдачи
3	10	5	Н/Д
1	12	8	13
2	18	9	18
4	14	6	14

Операция повторяется до тех пор, пока не останется невыполненных рейсов.
Мы получаем следующие результаты:

Расписание рейсов
№	Две даты	Время обработки
3	10	5
1	12	8
4	14	6
2	18	9

В этом порядке общее взвешенное опоздание равно 92.

Этот пример можно обобщить, чтобы запланировать любой список заданий, характеризующийся датой выполнения и временем обработки.

Производительность

Применение этой эвристики приведет к отсортированному списку задач, опоздание которых не может быть уменьшено соседним попарным обменом. ^[2] Сложность MDD $O(n)$ .

Вариации

Существует версия MDD, называемая взвешенной измененной датой выполнения (WMDD). ^[3] который учитывает веса. В таком случае функция оценки заменяется:

function wmdd(processed, task)
    return (1 / task.weight) * max(task.processTime, task.dueDate - processed)

Ссылки

^ Кеннет Р. Бейкер, JWM Бертран, Правило динамического приоритета для планирования в зависимости от сроков , Journal of Operations Management Vol. 3, стр. 37–42, 1982.
^ JC Nyirenda, Связь между измененным правилом срока родов и эвристикой Вилкерсона и Ирвина , ORiON Vol. 17, с 101–111, 2001.
^ Джон Дж. Канет, Сяомин Ли, Взвешенное модифицированное правило срока родов для последовательности для минимизации взвешенных опозданий , Журнал планирования № 7, стр. 261–276, 2004.

См. также

Планирование (вычисления)

[1] Кеннет Р. Бейкер, JWM Бертран, Правило динамического приоритета для планирования в зависимости от сроков , Journal of Operations Management Vol. 3, стр. 37–42, 1982.

[2] JC Nyirenda, Связь между измененным правилом срока родов и эвристикой Вилкерсона и Ирвина , ORiON Vol. 17, с 101–111, 2001.

[3] Джон Дж. Канет, Сяомин Ли, Взвешенное модифицированное правило срока родов для последовательности для минимизации взвешенных опозданий , Журнал планирования № 7, стр. 261–276, 2004.

[1]

[2]

[3]