Планирование на одной машине

Планирование для одного компьютера или для одного ресурса - это проблема оптимизации в компьютерных науках и исследованиях операций . Нам дается n заданий J ₁ , J ₂ , ..., J _n с различным временем обработки, которые необходимо запланировать на одной машине таким образом, чтобы оптимизировать определенную цель, например, пропускную способность .

Планирование для одного компьютера - это особый случай планирования для идентичных компьютеров , который сам по себе является особым случаем оптимального планирования заданий . Многие задачи, которые в целом являются NP-трудными, могут быть решены за полиномиальное время в случае одной машины. ^[1]^{: 10–20}

В стандартной записи с тремя полями для задач оптимального планирования заданий вариант для одной машины обозначается 1 в первом поле. Например, « 1 || » - это идентичная задача планирования машины без ограничений, цель которой - минимизировать сумму времени выполнения. ${\ displaystyle \ sum C_ {j}}$

Варианты

Задача минимизации времени изготовления 1 || , что является общей задачей для нескольких машин, тривиально для одной машины, поскольку время изготовления всегда идентично. Поэтому были изучены другие цели. Некоторые варианты решаются за полиномиальное время: ${\ displaystyle \ sum C _ {\ max}}$

Проблема 1 || - минимизация суммы времени завершения - может быть оптимально решена с помощью правила кратчайшего времени обработки (SPT): задания планируются в порядке возрастания времени их обработки . ${\ displaystyle \ sum C_ {j}}$ ${\ displaystyle p_ {j}}$
Проблема 1 || - минимизация взвешенной суммы времени выполнения - может быть оптимально решена с помощью правила первого взвешенного кратчайшего времени обработки (WSPT): задания планируются в порядке возрастания отношения . $\sum w_{j}C_{j}$ $p_{j}/w_{j}$
Проблема 1 | цепочки | , который является обобщением вышеупомянутой проблемы для заданий с зависимостями в виде цепочек, также может быть оптимально решен путем обобщения WSPT. $\sum w_{j}C_{j}$
Проблема 1 || стремится минимизировать максимальное опоздание . Для каждой работы j есть срок выполнения . Если он завершен после установленного срока, он страдает опозданием, определяемым как . 1 || может быть решена оптимально с помощью правила наиболее ранней даты выполнения (EDD): задания планируются в порядке возрастания их крайнего срока . $L_{\max }$ $d_{j}$ $L_{j}:=C_{j}-d_{j}$ $L_{\max }$ $d_{j}$
Проблема 1 | Prec | обобщает 1 || двумя способами: во-первых, он допускает произвольные ограничения приоритета для заданий; во-вторых, он позволяет каждой работе иметь произвольную функцию стоимости h _j , которая является функцией времени ее завершения (задержка - это частный случай функции стоимости). Максимальную стоимость можно минимизировать с помощью жадного алгоритма, известного как алгоритм Лоулера . $h_{\max }$ $L_{\max }$

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

В задаче 1 | | $r_{j}$ , каждое задание может иметь разное время выпуска, по истечении которого оно становится доступным для обработки. Наличие времени освобождения означает, что в некоторых случаях может быть оптимальным оставить машину бездействующей, чтобы дождаться важного задания, которое еще не запущено. Минимизировать максимальную задержку в этой настройке сложно. $L_{\max }$
В настройках с крайними сроками возможно, что, если работа будет завершена к крайнему сроку, будет прибыль p _j . В противном случае прибыли нет. Цель - максимизировать прибыль. Планирование на одной машине со сроками NP-трудное; Сахни ^[2] представляет как точные алгоритмы экспоненциального времени, так и алгоритм аппроксимации полиномиального времени.
Задания могут иметь интервалы выполнения . Для каждого задания j существует время обработки t _j и время начала s _j , поэтому оно должно выполняться в интервале [ s _j , s _j + t _j ]. Поскольку некоторые интервалы перекрываются, не все работы могут быть выполнены. Цель состоит в том, чтобы максимизировать количество выполненных заданий, то есть пропускную способность . В более общем смысле, каждая работа может иметь несколько возможных интервалов, и каждый интервал может быть связан с разной прибылью. Цель состоит в том, чтобы выбрать не более одного интервала для каждой работы, чтобы общая прибыль была максимальной. Дополнительные сведения см. На странице интервального планирования..
В более общем плане задания могут иметь временные окна , как со временем начала, так и с крайними сроками, которые могут быть больше, чем длина задания. Каждое задание можно запланировать в любом месте в пределах своего временного окна. Бар-Ной, Бар-Иегуда, Фройнд, Наор и Шибер ^[3] представляют приближение (1- ε ) / 2.

Методы решения

Многие методы решения были применены для решения задач планирования одной машины. Некоторые из них перечислены ниже.

Эвристика

Кратчайшее время обработки (SPT).

График SPT является оптимальным, если целью является минимизация среднего времени потока.

SPT-заказ - это заказ, основанный на времени обработки. Последовательность оставшихся заданий отсортирована по неубывающему времени обработки.

Самый ранний срок платежа (EDD)

График EDD является оптимальным, если цель состоит в том, чтобы минимизировать максимальное опоздание.

EDD-заказ - это заказ, основанный на установленном сроке. Последовательность оставшихся заданий отсортирована по неубывающей дате выполнения.

Примечание. «Опоздание» - это любое отклонение от установленного срока. Положительное опоздание - это «опоздание», отрицательное опоздание - «опоздание».

Алгоритм Ходжсона

Алгоритм Ходжсона дает оптимальное решение, если цель состоит в том, чтобы минимизировать количество заданий с опозданием больше нуля.

Вычислительная

использованная литература

^ Юджин Л. Лоулер, Ян Карел Ленстра, Александр HG Риннуй Кан, Дэвид Б. Шмойс (1993-01-01). «Глава 9 Последовательность и планирование: алгоритмы и сложность» . Справочники по исследованию операций и науке об управлении . 4 : 445–522. DOI : 10.1016 / S0927-0507 (05) 80189-6 . ISSN 0927-0507 .CS1 maint: несколько имен: список авторов ( ссылка )
^ Сахни, Сартадж К. (1976-01-01). «Алгоритмы планирования независимых задач» . Журнал ACM . 23 (1): 116–127. DOI : 10.1145 / 321921.321934 . ISSN 0004-5411 .
^ Бар-Ной, Амоц; Бар-Иегуда, Реувен; Фройнд, Ари; (Сеффи) Наор, Джозеф; Шибер, Барух (2001-09-01). «Единый подход к приблизительному распределению ресурсов и планированию» . Журнал ACM . 48 (5): 1069–1090. DOI : 10.1145 / 502102.502107 . ISSN 0004-5411 .

[:0-1] Юджин Л. Лоулер, Ян Карел Ленстра, Александр HG Риннуй Кан, Дэвид Б. Шмойс (1993-01-01). «Глава 9 Последовательность и планирование: алгоритмы и сложность» . Справочники по исследованию операций и науке об управлении . 4 : 445–522. DOI : 10.1016 / S0927-0507 (05) 80189-6 . ISSN 0927-0507 .CS1 maint: несколько имен: список авторов ( ссылка )

[2] Сахни, Сартадж К. (1976-01-01). «Алгоритмы планирования независимых задач» . Журнал ACM . 23 (1): 116–127. DOI : 10.1145 / 321921.321934 . ISSN 0004-5411 .

[3] Бар-Ной, Амоц; Бар-Иегуда, Реувен; Фройнд, Ари; (Сеффи) Наор, Джозеф; Шибер, Барух (2001-09-01). «Единый подход к приблизительному распределению ресурсов и планированию» . Журнал ACM . 48 (5): 1069–1090. DOI : 10.1145 / 502102.502107 . ISSN 0004-5411 .

[1]