Оптимальное планирование работы

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

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

Одноэтапные и многоэтапные задания

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

Машинные среды

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

• 1 : Планирование одной машины . Есть одна машина.
• P : Планирование идентичных машин . Есть $m$ параллельные машины, и они идентичны. Работа $j$ требует времени $p_{j}$ на любой машине это запланировано.
• Вопрос : Единообразное планирование машин . Есть $m$ параллельные машины, и у них разные заданные скорости. Работа $j$ на машине $i$ требует времени $p_{j}/s_{i}$.
• R : Планирование несвязанных машин . Есть $m$ параллельные машины, и они не связаны между собой – Джоб $j$ на машине $i$ требует времени $p_{ij}$.

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

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

• О : Проблема с открытым магазином . Каждая работа $j$ состоит из $m$ операции $O_{ij}$ для $i=1,\ldots ,m$. Операции можно планировать в любом порядке. Операция $O_{ij}$ должны быть обработаны для $p_{ij}$ единицы на машине $i$.
• F : Проблема с потоковым цехом . Каждая работа $j$ состоит из $m$ операции $O_{ij}$ для $i=1,\ldots ,m$, которые будут запланированы в заданном порядке. Операция $O_{ij}$ должны быть обработаны для $p_{ij}$ единицы на машине $i$.
• Дж : Проблема с магазином по работе . Каждая работа $j$ состоит из $n_{j}$ операции $O_{kj}$ для $k=1,\ldots ,n_{j}$, которые будут запланированы в таком порядке. Операция $O_{kj}$ должны быть обработаны для $p_{kj}$ агрегаты на отдельной машине $\mu _{kj}$ с $\mu _{kj}\neq \mu _{k'j}$ для $k\neq k'$.

Характеристики должности

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

• $p_{i}=p$, или $p_{ij}=p$: время обработки одинаково для всех заданий.
• $p_{i}=1$, или $p_{ij}=1$: время обработки для всех заданий равно 1 единице времени.
• $r_{j}$: для каждого задания указывается время выпуска, раньше которого оно не может быть запланировано, по умолчанию — 0.
• ${\text{online-}}r_{j}$: онлайн-проблема. Вакансии раскрываются во время их выпуска. В этом контексте производительность алгоритма измеряется его конкурентоспособностью .
• $d_{j}$: для каждой работы указан срок сдачи. Идея состоит в том, что каждое задание должно быть завершено до наступления установленного срока, и за задания, выполненные с опозданием, предусмотрены определенные штрафы. Этот штраф обозначается в объективном значении. Наличие должностной характеристики $d_{j}$ подразумевается неявно и не обозначается в названии задачи, если нет каких-либо ограничений, например $d_{j}=d$, предполагая, что все сроки выполнения равны некоторой заданной дате.
• ${\bar {d}}_{j}$: на каждую работу дается строгий срок выполнения. Любая работа должна быть завершена до установленного срока.
• pmtn : задания можно прервать и возобновить, возможно, на другом компьютере. Иногда также обозначается « prmp ».
• ${\text{size}}_{j}$: каждое задание включает в себя несколько машин, на которых оно должно быть запланировано одновременно. По умолчанию — 1. Это важный параметр в варианте, называемом планированием параллельных задач .

Отношения старшинства

Каждая пара двух заданий может иметь или не иметь отношение приоритета. Отношение приоритета между двумя заданиями означает, что одно задание должно быть завершено раньше другого. Например, если задание i является предшественником задания j в этом порядке, задание j может начаться только после завершения задания i.

• prec : На отношения старшинства не накладывается никаких ограничений.
• цепочки : каждое задание является предшественником не более одного другого задания и ему предшествует не более одного другого задания.
• дерево: отношения старшинства должны удовлетворять одному из двух ограничений.
  • intree: каждый узел является предшественником не более чем одного другого задания.
  • outtree: Каждому узлу предшествует не более одного задания.
• Противоположный лес: если граф отношений предшествования разбит на связные компоненты , то каждый связный компонент является либо внутренним, либо внешним деревом.
• sp-граф: Граф отношений предшествования представляет собой последовательно-параллельный граф .
• ограниченная высота : длина самого длинного направленного пути ограничена фиксированным значением. (Направленный путь — это последовательность заданий, в которой каждое задание, кроме последнего, является предшественником следующего задания в последовательности.)
• Порядок уровней : каждое задание имеет уровень, который представляет собой длину самого длинного пути, начинающегося с этого задания. Каждая работа с уровнем $k$ является предшественником каждой работы с уровнем $k-1$.
• интервальный порядок : Каждое задание $x$ имеет интервал [ s _x , e _x ) и задание $x$ является предшественником $y$ тогда и только тогда, когда конец интервала $x$ строго меньше начала интервала для $y$.=

При наличии отношения предшествования можно дополнительно предположить наличие временных задержек . Временной лаг между двумя заданиями — это количество времени, которое необходимо подождать после завершения первого задания, прежде чем начнется второе задание. Формально, если работа i предшествует работе j, то $C_{i}+\ell _{ij}\leq S_{j}$ должно быть правдой. Если нет временной задержки $\ell _{ij}$ указано, то оно считается равным нулю. Временные лаги также могут быть отрицательными. Отрицательный временной лаг означает, что второе задание может начаться в фиксированное время до завершения первого задания.

• ℓ : временной лаг одинаков для каждой пары заданий.
• $\ell _{ij}$: разные пары заданий могут иметь разные временные задержки.

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

• $t_{jk}$: Между завершением операции $O_{kj}$ работы $j$ на машине $k$ и начало эксплуатации $O_{k+1,j}$ работы $j$ на машине $k+1$, задержка транспортировки составляет как минимум $t_{jk}$единицы.
• $t_{jkl}$: Между завершением операции $O_{kj}$ работы $j$ на машине $k$ и начало эксплуатации $O_{l,j}$ работы $j$ на машине $l$, задержка транспортировки составляет как минимум $t_{jkl}$ единицы.
• $t_{k}$: Задержка транспортировки в зависимости от машины. Между завершением операции $O_{kj}$ работы $j$ на машине $k$ и начало эксплуатации $O_{k+1,j}$ работы $j$ на машине $k+1$, задержка транспортировки составляет как минимум $t_{k}$ единицы.
• $t_{kl}$: Задержка транспортировки в зависимости от пары машин. Между завершением операции $O_{kj}$ работы $j$ на машине $k$ и начало эксплуатации $O_{l,j}$ работы $j$ на машине $l$, задержка транспортировки составляет как минимум $t_{kl}$ единицы.
• $t_{j}$: Задержка транспортировки в зависимости от работы. Между завершением операции $O_{kj}$ работы $j$ на машине $k$ и начало эксплуатации $O_{l,j}$ работы $j$ на машине $l$, задержка транспортировки составляет как минимум $t_{j}$ единицы.

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

• rcrc : Также известен как рециркуляция или гибкая мастерская. Обещание о $\mu$ поднимается и для некоторых пар $k\neq k'$ у нас может быть $\mu _{kj}=\mu _{k'j}$. Другими словами, на одну и ту же машину можно назначить разные операции одной и той же работы.
• нет-подождите : операция $O_{k+1,i}$должен начинаться ровно тогда, когда операция $O_{k,i}$ завершает. Другими словами, как только одна операция задания завершается, следующая операция должна начаться немедленно. Иногда также обозначается как « nwt» .
• no-idle : ни одна машина не может простаивать между началом своего первого выполнения и концом последнего выполнения.
• ${\text{size}}_{j}$: Многопроцессорные задачи на идентичных параллельных машинах. Выполнение работы $j$ делается одновременно на ${\text{size}}_{j}$параллельные машины.
• ${\text{fix}}_{j}$: Многопроцессорные задачи. Каждая работа $j$предоставляется с набором машин ${\text{fix}}_{j}\subseteq \{1,\ldots ,m\}$, и нуждается одновременно во всех этих машинах для исполнения. Иногда также обозначается как «MPT».
• $M_{j}$: Универсальные машины. Каждая работа $j$ необходимо запланировать на одной машине из данного набора $M_{j}\subseteq \{1,\ldots ,m\}$. также обозначается Mj _Иногда .

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

Обычно цель состоит в том, чтобы минимизировать некоторую объективную ценность. Единственное отличие — это обозначение $\sum U_{j}$ где цель состоит в том, чтобы максимизировать количество заданий, завершенных до истечения установленного срока. Это также называется пропускной способностью . Целевое значение может быть суммой, возможно, взвешенной по некоторым заданным весам приоритета. $w_{j}$ за работу.

• - : Отсутствие объективного значения обозначается одинарной чертой. Это означает, что проблема состоит просто в создании допустимого планирования, удовлетворяющего всем заданным ограничениям.
• $C_{j}$: время завершения работы $j$. $C_{\max }$ — максимальное время выполнения; также известный как makepan . Иногда нас интересует среднее время завершения (среднее значение $C_{j}$ по всем j ), что иногда обозначается mft (среднее время окончания).
• $F_{j}$: Время выполнения задания представляет собой разницу между временем его завершения и временем выпуска, т.е. $F_{j}=C_{j}-r_{j}$.
• $L_{j}$: Опоздание . Каждая работа $j$ указан срок сдачи $d_{j}$. Опоздание на работу $j$ определяется как $C_{j}-d_{j}$. Иногда $L_{\max }$ используется для обозначения возможности решения проблемы со сроками. Действительно, при использовании двоичного поиска сложность технико-экономической версии эквивалентна минимизации $L_{\max }$.
• $U_{j}$: Пропускная способность . У каждой работы есть срок сдачи $d_{j}$. Существует удельная прибыль для работ, выполненных вовремя, т.е. $U_{j}=1$ если $C_{j}\leq d_{j}$ и $U_{j}=0$ в противном случае. Иногда смысл $U_{j}$ в литературе перевернут, что эквивалентно при рассмотрении варианта решения проблемы, но имеет огромное значение для аппроксимаций.
• $T_{j}$: Опоздание . Каждая работа $j$ указан срок сдачи $d_{j}$. Опоздание на работу $j$ определяется как $T_{j}=\max\{0,C_{j}-d_{j}\}$.
• $E_{j}$: Скороспелость . Каждая работа $j$ указан срок сдачи $d_{j}$. Раннее начало работы $j$ определяется как $E_{j}=\max\{0,d_{j}-C_{j}\}$. Эта цель важна для своевременного планирования.

Есть также варианты с несколькими целями , но они гораздо менее изучены.

Примеры

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

• $P_{2}\parallel C_{\max }$ – назначение каждого из $n$ задания передаются на одну из двух идентичных машин, чтобы минимизировать максимальное общее время обработки на машинах. Это оптимизационная версия проблемы с разделами.
• 1|предварительный| $L_{\max }$ – назначение одной машине процессов с общим ограничением приоритета, минимизирующим максимальную задержку.
• Р|pmtn| $\sum C_{i}$ – назначение задач переменному числу несвязанных параллельных машин, позволяющее вытеснять их и минимизировать общее время выполнения.
• J3| $p_{ij}\mid C_{\max }$ – задача цеха с тремя станками и единичным временем обработки, цель которой – минимизировать максимальное время завершения.
• $P\mid {\text{size}}_{j}\mid C_{\max }$ – назначение заданий $m$ параллельные идентичные машины, где каждое задание выполняется на нескольких машинах, на которых оно должно быть запланировано одновременно, что сводит к минимуму максимальное время выполнения. См. Планирование параллельных задач .

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

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

См. также

• Дробное планирование работы

Внешние ссылки

• Зоопарк планирования (Кристоф Дюрр, Сигрид Кнуст, Дэмиен Прот, Оскар К. Васкес): онлайн-инструмент для поиска оптимальной задачи планирования с использованием обозначений.
• Результаты по сложности задач планирования (Питер Брукер, Сигрид Кнуст): классификация задач оптимального планирования по тому, что известно об их сложности во время выполнения.