Нотация расписаний работ — это обозначения для класса задач оптимизации, связанных с планированием работ. Входными данными для таких задач являются работы (процессы или задания) и список машин или станков. Требуется составить расписание – назначение работ для машин. Расписание может оптимизировать определённые целевые функции.

Имеется много различных задач оптимального планирования работ, различных по природе работ, природе машин, по ограничениям на расписание и с различными целевыми функциями. Удобную нотацию для задачи оптимального планирования предложили Рональд Грэм, , и . Нотация состоит из трёх полей: α, β и γ.Каждое поле может быть списком слов, разделённых запятыми. Поле α описывает рабочую среду машин, β — характеристики и ограничения задачи, а γ — целевую функцию. С момента своего появления в конце 1970-х годов эта нотация постоянно расширялась, иногда непоследовательно. В результате сегодня некоторые проблемы встречаются с различными обозначениями в нескольких статьях.

Одностадийные / многостадийные работы В простых задачах оптимального планирования работ каждая операция j состоит из одной фазы выполнения с заданным временем обработки pj. В более сложных вариантах каждая операция состоит из нескольких фаз выполнения, которые могут выполняться последовательно или параллельно.

Рабочие среды машин Для задач планирования одностадийных работ имеется четыре главных категорий машинных сред:

1: Планирование для одного станка. Имеется одна машина. P: Планирование для одинаковых станков. Имеется параллельных машин и они идентичны. Работа занимает времени на любой машине. Q: Планирование для однородных станков. Имеется параллельных машин и они имеют различные скорости. Работа на машине занимает времени. R: . Имеется параллельных машин и они не связаны – работа на машине занимает времени.

Эти буквы могут сопровождаться числом машин, которое затем фиксируется. Например, P2 означает наличие двух параллельных идентичных машин. Pm указывает на наличие m параллельных идентичных машин, где m является фиксированным параметром. В отличие от этого, P означает наличие m параллельных идентичных машин, но m не фиксировано (оно является частью входных данных).

В задачах многостадийного планирования работ существуют и другие варианты машинной среды.

O: . Любая работа состоит из операция для . Операции могут быть запланированы в любом порядке. Операция должны выполняться на станке в течение единиц времени. F: Задача поточной линии. Любая работа состоит из операций для , которые должны быть запланированы в заданном порядке. Операция требует обработки на станке в течение единиц времени. J: . Любая работа состоит из операций для , которые должны быть запланированы в указанном порядке. Операция должна быть выполнена в течение единиц времени на выделенном станке , при этом для .

Характеристики работы

Все продолжительности работ предполагаются целыми числами. В некоторых старых исследовательских статьях они предполагались рациональными.

или : время выполнения работ для всех работ одинаково. или : время выполнения работ равно единице времени для всех работ. : для каждой работы дано время готовности, до которого её нельзя запланировать. По умолчанию это значение равно 0. : онлайн-задача. Задания становятся известны в момент их готовности. См. статью . : для каждого задания указан срок выполнения. Предполагается, что каждое задание должна быть завершена до наступления срока, и за просроченные задания начисляется штраф. Этот штраф отражается в целевой функции. Присутствие характеристики задания подразумевается по умолчанию и не указывается в названии задачи, если нет ограничений, например, означает, что все сроки выполнения равны некоторой заданной дате. : для каждого задания установлен строгий крайний срок. Каждое задание должно быть завершено до наступления этого срока. pmtn: задания могут быть прерваны и возобновлены, возможно, на другой машине. Иногда также обозначается как 'prmp'. : каждой работе даётся число станков, на которые работа должна быть запланирована одновременно. По умолчанию это 1. Это важный параметр в варианте, называемом .

Отношения предшествования Каждая пара из двух заданий может иметь или не иметь отношение предшествования. Отношение предшествования между двумя заданиями означает, что одно задание должно быть завершено до другого. Например, если задание i является предшественником задания j, то задание j может начаться только после завершения задания i. prec: На отношения предшествования не накладывается никаких ограничений. chains: Каждое задание является предшественником не более чем одному другому заданию и предшествуется не более чем одному другому заданию. tree: Отношения предшествования должны удовлетворять одному из двух ограничений. intree: Каждое задание является предшественником не более чем одному другому заданию. outtree: Каждое задание предшествуется не более чем одному другому заданию. opposing forest: Если граф отношений предшествования разбит на связные компоненты, то каждая связная компонента является либо intree, либо outtree. sp-graph: Граф отношений предшествования является параллельно-последовательным графом. bounded height: Длина самого длинного направленного пути ограничена фиксированным значением. (Направленный путь — это последовательность заданий, где каждое задание, кроме последнего, является предшественником следующего задания в последовательности.) level order: Каждое задание имеет уровень, который равен длине самого длинного направленного пути, начинающегося с этого задания. Каждое задание уровня является предшественником каждого задания уровня . interval order: Каждое задание имеет интервал и работа является предшественницей работы тогда и только тогда, когда конец интервала задания строго меньше начала интервала задания .

При наличии отношения предшествования можно также предположить временны́е задержки. Временна́я задержка между двумя заданиями — это время, которое должно пройти после завершения первого задания, прежде чем второе задание сможет начаться. Формально, если задание i предшествует заданию j, то должно выполняться условие . Если временна́я задержка не указана, то предполагается, что она равна нулю. Временны́е задержки могут быть и отрицательными. Отрицательная временная задержка означает, что вторая задача может начаться за фиксированное время до завершения первой задачи.

ℓ: Временна́я задержка одинакова для каждой пары заданий. : Различные пары заданий могут иметь разные временны́е задержки.

Задержки на транспортировку

: Время транспортировки между завершением операции работы на станке и началом операции работы на станке составляет не менее единиц. : Время транспортировки между завершением операции для работы на станке и началом операции для работы на станке составляет не менее единиц. : Время транспортировки, зависящее от станка. Между завершением операции работы на станке и началом операции работы на станке существует задержка транспортировки не менее единиц. : Задержка транспортировки, зависящая от пары машин. Между завершением операции для задания на станке и началом операции для задания на станке возникает задержка транспортировки, которая составляет не менее единиц времени. : Задержка транспортировки, зависящая от задания. Между завершением операции для задания на станке и началом операции для задания на станке возникает задержка транспортировки, которая составляет не менее единиц времени.

Различные ограничения

rcrc: Также называется рециркуляцией или гибким цехом. В этом случае ограничение на снимаются и для некоторых пар может быть . Иными словами, различные операции одной и той же работы могут быть назначены на одну и ту же машину. no-wait: Операция должна начинаться ровно в тот момент, когда завершается операция . Другими словами, как только одна операция работы заканчивается, следующая операция должна начаться немедленно. Иногда также обозначается как 'nwt'. no-idle: Ни одна машина не может простаивать между началом своего первого выполнения и окончанием своего последнего выполнения. : Многопроцессорные задачи на идентичных параллельных машинах. Выполнение задания происходит одновременно на станках. : Многопроцессорные задачи. Каждое задание job задаётся набором машин и требует одновременного использования всех этих машин для выполнения. Иногда также обозначается как 'MPT'. : Многоцелевые машины. Каждое задание должно быть запланировано на одной машине из заданного набора . Иногда также обозначается как Mj.

Целевые функции

Обычно цель состоит в минимизации некоторого целевого значения. Исключением является обозначение , где цель состоит в максимизации количества заданий, завершённых до установленного срока. Это также называют пропускной способностью. Целевое значение может представлять собой сумму, возможно, взвешенную по некоторым заданным весовым коэффициентам приоритета для каждого задания.

-: Отсутствие целевой функции обозначается прочерком. Это означает, что задача состоит просто в создании осуществимого расписания, удовлетворяющего всем заданным ограничениям. : время завершения работы . — это максимальное время завершения, известное также как . Иногда нас интересует среднее время завершения (среднее значение по всем j), которое иногда обозначается как mft (mean finish time — среднее время окончания). : Время в работе — это разница между временем выполнения задания и временем поступления, то есть . : . Каждому заданию назначается срок выполнения . Опоздание задания определяется как . Иногда для обозначения выполнимости задачи с крайними сроками используется . Действительно, используя двоичный поиск, сложность версии на выполнимость эквивалентна минимизации . : Пропускная способность. Каждому заданию назначается срок выполнения . Задания, завершённые вовремя, приносят единичную прибыль, то есть , если и в противном случае. Иногда в литературе значение инвертируется, что эквивалентно при рассмотрении решаемой версии задачи, но существенно влияет на аппроксимации. : . Каждому заданию присваивается срок выполнения . Запаздывание задания определяется как . : . Каждому заданию присваивается срок выполнения . Раннее выполнение задания определяется как . Эта цель важна для планирования точно в срок. Существуют также варианты с многокритериальной оптимизацией, но они изучены гораздо меньше.

Пример Вот несколько примеров задач, определённых с использованием вышеупомянутой нотации.

– назначение группу из заданий одной из двух идентичных машин с целью минимизации максимального суммарного времени обработки на машинах. Это оптимизирующий вариант задачи разбиения 1|prec| – назначение заданий с общими ограничениями предшествования на одну машину с целью минимизации максимального опоздания. R|pmtn| – назначение заданий по переменному числу несвязанных параллельных машин с возможностью прерывания с целью минимизации суммарного времени завершения. J3|| – задача производственного цеха с тремя машинами и единичным временем обработки, целью которой является минимизация максимального времени завершения – назначение заданий на параллельных машин, где каждое задание требует одновременного выполнения на определённом количестве машин, с целью минимизации максимального времени завершения. См. статью .

Другик варианты

Все рассмотренные выше варианты являются детерминированными, поскольку планировщику известны все данные. Существуют также стохастические варианты, в которых данные неизвестны заранее или могут случайным образом изменяться. В игре с балансировкой нагрузки, каждая задача принадлежит стратегическому агенту, который может решить, куда ее запланировать. Равновесие Нэша в этой игре может быть неоптимальным. Ауманн и Домбб оценивают неэффективность равновесия в нескольких играх с балансировкой нагрузки.

См. также

Балансировка нагрузки: Оптимальная балансировка нагрузки является альтернативным термином для оптимального планирования заданий.

Примечания

Ссылки