Постановка основной задачи теории расписаний. Случай одной машины.
Предмет теории расписаний - это составление календарных планов, оптимальных относительно того или иного критерия. Задачи теории рас-писаний с точки зрения программирования - это всегда те или иные задачи упорядочения.
Проиллюстрируем простым примером специфику этих задач.
Пусть на некотором производственном участке имеется два
станка - Т1 и Т2, - на которых изготавливаются три детали - Д1, Д2 и Д3, причем каждая сначала обрабатывается на станке Т1, а затем на станке Т2. Время обработки каждой детали на каждом станке известно и задается следующей таблицей (будем считать, что все - в часах):
станок\деталь | Д1 | Д2 | Д3 |
Т1 | |||
Т2 |
Если детали запустить на обработку в последовательности Д2, Д1, Д3 (т.е. сначала - Д2, потом - Д1, а потом - Д3), то весь производственный процесс закончится через 8 часов, а если эти же детали запустить на эти же станки в последовательности Д3, Д1, Д2, то весь производственный процесс закончится только через 11 часов.
Существуют различные способы изображать расписания в подобных
задачах; все они включают, как правило, серьезный графический элемент для наглядности (Гант-карты, ленточные графики и т.д.)
Обратимся к первому классу задач теории расписаний, который приня-то называть задачи для одной машины.
Итак, имеется одна машина, на которой производятся работы в той или иной последовательности - работы из множества ; пусть - фактическая продолжительность выполнения i -ой работы, - начало и конец фактического выполнения работы (так что ), - директивное время выполения i -ой работы (т.е. время, в течение которого работы должна быть выполнена по плану), - стоимость ожидания в единицу времени i -ой работы.
Перерывы в выполнении работ не допускаются.
Пусть ; это - задержка i -ой работы по сравнению с директивным временем на производственном участке. Положим
;
это - суммарный штраф за простой при выполнении работ по тому или иному плану. Пусть, далее,
;
это - максимальный среди работ штраф за простой. Чем он меньше, тем равномернее издержки, доставляемые работами.
Наконец, пусть
;
это - сумма штрафов, связанных с ожиданием работ в системе.
Часто фиксируют величину
-
суммарное время выполнения всех работ.
Приведенные выше три критерия - F1, F2 и F3 - являются наиболее распространенными в рассмотрениях расписаний для одной машины. В каждом конкретном случае задача состоит в том, чтобы подобрать такую последовательность выполнения работ, чтобы соответствующий критерий обратился в минимум.
Можно доказать следующее утверждение:
пусть работы занумерованы так, что
;
тогда, если их запустить на исполнение в порядке возрастания номеров, то критерий F3 обратится в минимум.
Можно доказать также, что действия по нижеследующему алгоритму приводят к минимуму критерия F2:
Шаг 0. Находим .
Шаг 1. Среди всех еще неупорядоченных работ находим такую работу l, что
где , причем минимум вычисляется только по множеству еще неупорядоченных работ.
Шаг 2. Работу l назначают последней к исполнению среди еще неупоря-доченных работ и исключают из рассмотрения. Если множество оставшихся работ пусто, то процесс упорядочения закончен. Если множество оставшихся работ непусто, заменим T на и переходим к Шагу 1.
Заметим, в заключение, что относительно критерия F1 в общем случае неизвестен алгоритм, отличный от прямого перебора возможностей.