Простейшие задачи теории Расписаний

Основные обозначения

Задачи одного исполнителя на минимакс:
Исполнитель должен последовательно выполнить n работ
Каждая j-я работа имеет известную длительность pj
Работы можно выполнять в любом порядке и начинать в произвольный момент времени
Каждая работа выполняется с самого начала и должна быть выполнена полностью прежде чем начнется выполнение следующей
Разрывы в исполнении работ невыгодны
Чем скорее будет выполнена любая работа, тем лучше (задача на минимакс)
Время окончания работ tj зависят от перестановки π (порядок выполнения работ)
T{ t1(π), t2(π),…, tn(π)} – называется расписанием

Задача красильщика
Красильщик должен окрасить n предметов. Для окраски j-го предмета
требуется время pj. По окончании окраски j-й предмет должен еще
сохнуть в спец. камере время bj после чего он считается готовым. В каком
порядке нужно красить предметы, чтобы последний в просушке был готов
как можно раньше?
Каждой j-ой работе можно сопоставить штрафную функцию
ψ(t) = tj+ bj
Задача: Построить такое расписание Т(π), чтобы
минимизировать f = max(ψj)

Теорема 1: Оптимальное расписание в задаче красильщика получается упорядочением работ по убыванию bj
Доказательство: Пусть π’ – перестановка, для которой выполняется свойство:
bπ’(1) ≥ bπ’(2) ≥ … ≥ bπ’(n) . Предположим противное: π’ не является оптимальной
Тогда существует некоторая оптимальная перестановка π0 такая, что
f(T(π0)) < f(T(π0))
Так как π0 ≠ π’ , то в перестановке π0 найдется пара работ α и β таких, что
∝ β , но bα < bβ. Пусть суммарная длительность работ, стоящих в
перестановке π0 перед работой α равна τ
Тогда, учитывая, что bα < bβ : max(τ + pα + bα , τ + pα + pβ + bβ) = τ + pα + pβ + bβ
Составим перестановку π1 , в которой работы α и β переставлены местами:

тогда вклад в f от работы β равен τ + pβ + bβ а от работы α равен: τ + pβ + pα + bα
Можно заметить: τ + pβ + bβ < τ + pα + pβ + bβ (что является max для π0) т.к. pα > 0;
и одновременно τ + pβ + pα + bα < τ + pα + pβ + bβ , т.к. bα < bβ
Поэтому f(π1) ≤ f(π0) . Если в перестановке π1 присутствует еще одна такая пара, то с ней можно поступить аналогично и т.д. В результате получим перестановку в которой выполняется свойство: bπ’(1) ≥ bπ’(2) ≥ … ≥ bπ’(n) . Ч.т.д.
«Небольшое» усложнение задачи: обычно не все работы известны в начальное
время, они могут появляться в моменты времени rj. Таким образом, работе j
сопоставлен не только «хвост» bj, но и возможно ранние начала rj.
Такая задача может быть решена только «перебором»!!!
В Календарном планировании каждой работе сопоставлен директивный срок
выполнения dj. Отклонением от директивного срока называют величину:
lj(T(π)) = tj(T) – dj
В различных задачах могут рассматриваться штрафные функции для
отклонений как положительных, так и отрицательных.

Задача Джексона (1954 – 1955 г.)
Рассматриваются n работ, для каждой из которых определены длительности pj и директивные сроки выполнения dj. Построить такое расписание Т(π), чтобы минимизировать сумму отклонений f = ∑ ( tj(T) – dj)
Теорема 2: Оптимальное расписание T(π’) в задаче Джексона достигается упорядочением работ по возрастанию их директивных сроков.
dπ’(1) ≤ dπ’(2) ≤ … ≤ dπ’(n)
Док-во – аналогично док-ву Теоремы 1.
Алгоритм Лившица: Оптимальный порядок работ строится, начиная с конца. При
любом порядке последняя работа окончится в момент ω = ∑ pj
Оценим значения штрафных функций задачи и найдем min ψj. Пусть он
достигается на k-й работе: min ψj = ψk
Положим π’(n) = k и перейдем к задаче меньшего размера, полагая
n = n – 1; ω = ω - pk; J = J \ k
Повторяя эту процедуру n раз, найдем оптимальную перестановку.

Задачи одного исполнителя на минисумму
Задача 1: Все n работ находятся в системе с момента t = 0. Каждая j-я работа
Покидает систему в момент tj(Т). Минимизировать среднее время пребывания
работ в системе: f(T) = ⋅ ∑ tj(Т).
Теорема (Смит): Задача минимизации среднего времени решается
упорядочением работ по возрастанию длительностей.
Задача 2: В условиях предыдущей задачи учитывается дополнительно
различная стоимость cj пребывания работ в системе. Минимизации подлежит
следующий функционал: f(π) = ∑ (cj ⋅ tj).
Теорема ( Мак-Нотон): Задача минимизации суммарного взвешенного
времени пребывания работ в системе решается упорядочением
работ по возрастанию параметра pj / cj.
Док-во этих теорем– аналогично док-ву Теоремы 1.

Решение аналогичных задач:
Отклонение окончания j-й работы от директивного срока dj : lj = tj(T) – dj
Минимизируемый функционал:
fl = ∑(cj ⋅ lj) = ∑(cj ⋅ (tj - dj)
Задача решается алгоритмом Мак-Нотона, так как функционалы отличаются на константу
Запоздание окончания j-й работы от директивного срока dj : zj = ( tj(T) – dj )+
Минимизируемый функционал:
fl = ∑(cj ⋅ zj) = ∑(cj ⋅ (tj - dj)+
Задача решается только перебором (NP-полная задача)

Случаи разрывной функции штрафа
Задача 1 (Мур): Минимизировать число запоздавших работ.
В этом случае штрафная функция выглядит так
Алгоритм Ходжсона:
Упорядочить все работы в порядке возрастания dj (если di = dj, то первой
ставится работа с меньшим номером). В результате получим перестановку
π = (π(1), π(2),…, π(k), …, π(n);
k: = 0;
k: = k + 1. Если работа k – отмечена или k ≥ n, то полученная перестановка π’ – оптимальная. Конец.
Если tπ(k) ≤ dπ(k) , то перейти к 3.
В случае, если tπ(k) > dπ(k) , найти из работ π(1), π(2),…, π(k) работу самой большой длительности. Пусть это будет работа j = π(r). Поставить работу j в конец, а следующие за ней до π(k)-й работы включительно сдвинуть к началу, то есть порядок π=(π(1), π(2),…, π(r-1), j = π(r), π(r+1),…, π(k),…,π(n)) преобразовать в порядок π’ =(π(1), π(2),…, π(r-1), π(r+1),…, π(k),…, π(n), j ) .
Отметить работу j. Перейти к 3).
В случае, если штрафная функция имеет вид:
задача является универсальной переборной.

Задачи о нескольких исполнителях
Имеется два идентичных исполнителя и n работ с длительностями p1, p2, … ,pn
Нет никаких ограничений ни на разбрасывание, ни на порядок. Необходимо
минимизировать время, когда закончит работу последний из двух исполнителей.
Для решения необходимо разбросать работы так, чтобы суммы длительностей
работ, доставшихся каждому исполнителю были как можно более одинаковыми.
(Идентична «Задаче о камнях», которая решается только перебором)
Задача С.Джонсона о двух станках: На двух станках М1 и М2 нужно изготовить
n деталей. Для изготовления j-й детали нужно проделать 2 операции – сначала
первую на станке М1 с длительностью aj, а потом(возможно после перерыва) –
вторую, на станке М2 с длительностью bj. Требуется найти такие порядки
выполнения операций на обоих станках, чтобы как можно раньше изготовить
все детали.
Алгоритм (Джонсон) решения этой задачи опирается на том свойстве, что
f( T( πα, πβ )) ≥ f( T( πα, πα ))