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

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

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

Одноэтапные задания против многоэтапных заданий

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существуют также варианты с несколькими целями , но они гораздо менее изучены. ^[2]

Примеры

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

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

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

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

Смотрите также

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

Ссылки

1. Graham, RL; Lawler, EL; Lenstra, JK; Rinnooy Kan, AHG (1979). «Оптимизация и аппроксимация в детерминированном секвенировании и планировании: обзор» (PDF) . Труды Института передовых исследований по дискретной оптимизации и системным приложениям Группы системных наук НАТО и Симпозиума по дискретной оптимизации . Elsevier. стр. (5) 287–326.
2. Eugene L. Lawler, Jan Karel Lenstra, Alexander HG Rinnooy Kan, David B. Shmoys (1993-01-01). "Глава 9 Последовательность и планирование: Алгоритмы и сложность". Справочники по исследованию операций и науке управления . 4 : 445–522. doi :10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN  0927-0507.{{cite journal}}: CS1 maint: multiple names: authors list (link)
3. B. Chen, CN Potts и GJ Woeginger . "Обзор машинного планирования: сложность, алгоритмы и аппроксимируемость". Handbook of Combinatory Optimization (том 3) (редакторы: D.-Z. Du и P. Pardalos), 1998, Kluwer Academic Publishers. 21-169. ISBN 0-7923-5285-8 (HB) 0-7923-5019-7 (набор) 
4. Хоровиц, Эллис; Сахни, Сартай (1976-04-01). «Точные и приближенные алгоритмы планирования неидентичных процессоров». Журнал ACM . 23 (2): 317–327. doi : 10.1145/321941.321951 . ISSN  0004-5411. S2CID  18693114.
5. Ауманн, Йонатан; Домб, Яир (2010). Контогианнис, Спирос; Кутсупьяс, Элиас; Спиракис, Пол Г. (ред.). "Эффективность по Парето и приближенная эффективность по Парето в играх маршрутизации и балансировки нагрузки". Алгоритмическая теория игр . Конспект лекций по информатике. Берлин, Гейдельберг: Springer: 66–77. doi :10.1007/978-3-642-16170-4_7. ISBN 978-3-642-16170-4.

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

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