Расписания: две цели, два критерия, один приём

Если ты знаешь, какой критерий отвечает за сумму завершений, какой за максимальное опоздание, и умеешь доказать оба обменом соседних, листай до «Теперь сам».

Как думаешь, в каком порядке пускать

Четыре задачи длительностью 8, 1, 3, 2 часа, один исполнитель, порядок наш. В каком порядке их пускать?

Вопрос неполон, и это главное в уроке: пока не сказано, ЧТО мы минимизируем, ответа нет. Если важно, чтобы в среднем ждали меньше, - один порядок. Если у задач есть сроки и важно не опоздать - другой. Если за опоздание платят разную неустойку - третий.

На что это похоже

Очередь в магазине. Человека с двумя йогуртами пропускают вперёд - и общее время ожидания в очереди падает, потому что его тридцать секунд добавятся к ожиданию одного человека, а не наоборот. Но если у кого-то в очереди поезд через десять минут, правило меняется: вперёд идёт не самый быстрый, а самый срочный. Магазинная вежливость и теория расписаний здесь говорят одно и то же.

Механизм: две цели и два критерия

ОБОЗНАЧЕНИЯ
t_i  - длительность задачи
C_i  - момент её ЗАВЕРШЕНИЯ при выбранном порядке
d_i  - срок (deadline), к которому её ждут
L_i  = C_i − d_i  - опоздание (может быть отрицательным)

ЦЕЛЬ 1: минимизировать Σ C_i  (сумма времён завершения)
    критерий: по возрастанию t_i - КОРОТКИЕ ВПЕРЁД (SPT, shortest processing time)
    длительности важны, сроки не участвуют

ЦЕЛЬ 2: минимизировать max L_i  (самое большое опоздание)
    критерий: по возрастанию d_i - БЛИЖАЙШИЙ СРОК ВПЕРЁД
    (EDF, earliest deadline first; для непрерываемых задач на одной машине
     то же правило называют EDD или правилом Джексона)
    в КРИТЕРИЙ длительности не входят - сами опоздания, конечно,
    считаются через них

ЦЕЛЬ 3: минимизировать Σ w_i · C_i  (взвешенная сумма завершений)
    критерий: по убыванию w_i / t_i - ПРАВИЛО СМИТА
    при всех w_i = 1 превращается в SPT

ВЫКЛАДКА ДЛЯ ПРАВИЛА СМИТА (обмен соседних i, j: было i раньше j)

пусть до пары прошло время S.
было:   w_i·(S + t_i) + w_j·(S + t_i + t_j)
стало:  w_j·(S + t_j) + w_i·(S + t_j + t_i)
разница (было − стало) = w_j·t_i − w_i·t_j

обмен выгоден ровно когда w_j·t_i > w_i·t_j, то есть когда
w_j/t_j > w_i/t_i - «большее отношение вперёд».
При равных отношениях разница НУЛЕВАЯ: порядок внутри группы не важен.
При всех w = 1 условие превращается в t_i > t_j - это SPT

ПРИЁМ ДОКАЗАТЕЛЬСТВА - ОБМЕН СОСЕДНИХ

1. предположить, что в оптимуме есть ПАРА СОСЕДЕЙ «не в том порядке»
2. поменять их местами
3. показать, что цель не выросла (а для строгого случая - уменьшилась)
4. значит оптимум можно привести к нужному порядку, не ухудшив

Почему берут именно соседей: при перестановке двух СОСЕДНИХ задач ничего не меняется ни для тех, кто был раньше, ни для тех, кто позже - сумма пары та же. Поэтому в выкладке остаются только два слагаемых, и всё считается в три строки. Перестановка далёких задач затронула бы всех между ними.

Правило

Критерий расписания определяется целью, а не задачами. Сумма времён завершения Σ C_i - короткие вперёд (SPT), и доказывается обменом соседних: если длинная стоит перед короткой, их перестановка уменьшает сумму на t_i − t_j. Максимальное опоздание max L_i - ближайший срок вперёд (EDF), причём длительности в критерии не участвуют. Взвешенная сумма Σ w_i·C_i - по убыванию w_i / t_i (правило Смита). Обмен СОСЕДНИХ работает потому, что такая перестановка не затрагивает остальные задачи: в выкладке остаются два слагаемых. Как только машин становится больше одной или между задачами появляются зависимости, жадность перестаёт быть точной: такие постановки уже NP-трудны - например, минимизация времени окончания всех работ на двух машинах есть задача о разбиении (разложить числа на две группы с равными суммами).

Разбор: SPT против обратного порядка на числах

Четыре задачи: 8, 1, 3, 2.

ПОРЯДОК ПО ВОЗРАСТАНИЮ: 1, 2, 3, 8
завершения:  1, 3, 6, 14        Σ C = 24

ПОРЯДОК ПО УБЫВАНИЮ: 8, 3, 2, 1
завершения:  8, 11, 13, 14      Σ C = 46

ПОРЯДОК КАК ДАНО: 8, 1, 3, 2
завершения:  8, 9, 12, 14       Σ C = 43

Разница почти вдвое, и код отличается одним словом в сортировке. Обрати внимание, что ПОСЛЕДНЕЕ завершение (14) во всех трёх случаях одинаково: суммарная работа не зависит от порядка. Порядок меняет только то, сколько раз каждая длительность входит в сумму.

почему: задача, стоящая на k-м месте, своей длительностью
        задерживает ВСЕХ, кто после неё - то есть входит в сумму (n − k + 1) раз

Σ C = n·t_(1) + (n−1)·t_(2) + ... + 1·t_(n)

самый большой множитель n стоит у ПЕРВОЙ задачи - значит первой
должна быть самая короткая

Это уже доказательство, причём без обмена: в сумме каждая длительность умножается на свой множитель из набора n, n−1, ..., 1, и чтобы сумма произведений была наименьшей, большие множители должны стоять у маленьких длительностей. Строго это называется перестановочным неравенством, но проверить можно и обменом: поменяй местами два соседних слагаемых и посмотри на разницу - она равна t_i − t_j, то есть выкладка Смита при всех w = 1. Обменная выкладка переносится на взвешенный случай, а подсчёт множителей - нет.

Разбор: EDF и почему длительности не важны

Три задачи: сроки и длительности.

задача   длительность   срок
   A          4           5
   B          2           3
   C          3          11

ПОРЯДОК EDF (по сроку: B(3), A(5), C(11)):
B: завершилось в 2,  срок 3   → опоздание −1
A: завершилось в 6,  срок 5   → опоздание +1
C: завершилось в 9,  срок 11  → опоздание −2
max опоздание = 1

ПОРЯДОК SPT (по длительности: B(2), C(3), A(4)):
B: завершилось в 2,  срок 3   → −1
C: завершилось в 5,  срок 11  → −6
A: завершилось в 9,  срок 5   → +4
max опоздание = 4

Критерий, оптимальный для суммы завершений, дал опоздание вчетверо больше. И наоборот: у EDF сумма завершений 2 + 6 + 9 = 17 против 2 + 5 + 9 = 16 у SPT - он проигрывает по ДРУГОЙ цели. Два критерия не соревнуются: каждый оптимален для своей меры.

Доказательство EDF обменом соседних:

пусть в расписании соседние задачи i, j идут в порядке i, j, но d_i > d_j
    (срок первой ДАЛЬШЕ, то есть порядок «не по EDF»)

поменяем их местами. Пусть до пары прошло время S.
было:   L_i = S + t_i − d_i          L_j = S + t_i + t_j − d_j
стало:  L_j' = S + t_j − d_j         L_i' = S + t_j + t_i − d_i

максимум ПОСЛЕ обмена: max(L_j', L_i') 
    L_j' = S + t_j − d_j  <=  S + t_i + t_j − d_j = L_j      (убрали t_i)
    L_i' = S + t_i + t_j − d_i  <=  S + t_i + t_j − d_j = L_j   (так как d_i > d_j)

то есть ОБА новых опоздания не больше прежнего L_j, а значит
максимум по всему расписанию не вырос. Остальные задачи не затронуты.   ∎

Обрати внимание на изящество: нам не нужно было сравнивать t_i и t_j ни разу. Поэтому длительности и не входят в критерий.

Что ломается без этого

Первое: выбрать критерий, не назвав цель: «оптимальное расписание» без указания меры - бессмысленная фраза, и ровно на ней чаще всего спорят в рабочих обсуждениях. Второе: применять SPT там, где важны сроки: в примере выше это дало опоздание 4 вместо 1. Третье: переносить правило на ДВЕ и более машин: уже минимизация времени окончания всех работ на двух машинах NP-трудна (это задача о разбиении), и жадность «самую длинную на свободную машину» даёт лишь приближение. Четвёртое: забыть, что EDF минимизирует МАКСИМАЛЬНОЕ опоздание, а не число опоздавших задач и не сумму опозданий - для этих целей нужны другие алгоритмы. Пятое: в правиле Смита перепутать направление: сортировать надо по УБЫВАНИЮ отношения w/t, то есть вперёд идут задачи с большим весом на единицу времени.

Зачем это в работе

SPT и EDF - это буквально планировщики. В операционных системах shortest job first даёт минимальное среднее время отклика и используется там, где длительность известна или предсказуема; EDF - основной алгоритм систем реального времени (им планируют задачи в промышленных контроллерах, аудио- и видеотрактах), и для него есть точный критерий осуществимости: если задачи периодические и срок каждой равен её периоду, то на одном процессоре EDF с прерываниями успевает ко всем срокам тогда и только тогда, когда суммарная загрузка - сумма отношений «время выполнения к периоду» - не больше единицы. В прикладных сервисах то же самое всплывает в очередях: сначала короткие запросы (меньше среднее ожидание) против сначала срочные (меньше нарушений обещанного срока) - это и есть выбор между двумя целями, и обсуждать его надо в этих терминах. Правило Смита - основа взвешенных очередей: вес обычно означает «важность клиента», и отношение вес / длительность ровно отвечает на вопрос «кого пустить вперёд».

Теперь сам

Задачи с весами: (t = 2, w = 1), (t = 1, w = 3), (t = 4, w = 2). Минимизируй Σ w_i·C_i. Назови порядок и посчитай значение.

задача        w / t
(t=1, w=3)    3.0    ← первая
(t=4, w=2)    0.5    ← вторая
(t=2, w=1)    0.5    ← третья (ничья с предыдущей)

порядок (1, 4, 2):  завершения 1, 5, 7
Σ w·C = 3·1 + 2·5 + 1·7 = 3 + 10 + 7 = 20

(1, 2, 4):  C = 1, 3, 7   →  3·1 + 1·3 + 2·7 = 20     ← ничья, ожидаемо
(2, 1, 4):  C = 2, 3, 7   →  1·2 + 3·3 + 2·7 = 25
(2, 4, 1):  C = 2, 6, 7   →  1·2 + 2·6 + 3·7 = 35
(4, 1, 2):  C = 4, 5, 7   →  2·4 + 3·5 + 1·7 = 30
(4, 2, 1):  C = 4, 6, 7   →  2·4 + 1·6 + 3·7 = 35