Планирование одной машины

Планирование одной машины или планирование одного ресурса — это проблема оптимизации в информатике и исследовании операций . Нам даны n заданий J ₁ , J ₂ , ..., J _n с различным временем обработки, которые необходимо запланировать на одной машине таким образом, чтобы оптимизировать определенную цель, например, пропускную способность .

Планирование одной машины — это особый случай планирования идентичных машин , которое само по себе является частным случаем оптимального планирования заданий . Многие задачи, которые вообще являются NP-трудными, могут быть решены за полиномиальное время в одномашинном случае. ^[1]^: 10–20

В стандартной записи с тремя полями для задач оптимального планирования заданий вариант с одной машиной обозначается цифрой 1 в первом поле. Например, « 1|| $\sum C_{j}$ « — это задача планирования для одной машины без ограничений, цель которой — минимизировать сумму времени завершения.

Задача минимизации makepan 1|| $C_{\max }$ , что является общей целью для нескольких машин, тривиально для одной машины, поскольку период обработки всегда идентичен. Поэтому были изучены другие цели. ^[2]

Минимизация суммы времени завершения

Проблема 1|| $\sum C_{j}$ направлен на минимизацию суммы времени завершения. Оптимально ее можно решить с помощью правила «Сначала наименьшее время обработки» ( SPT ): задания планируются в порядке возрастания времени их обработки. $p_{j}$ .

Проблема 1|| $\sum w_{j}C_{j}$ Целью является минимизация взвешенной суммы времени завершения. Оптимально ее можно решить с помощью правила взвешенного наименьшего времени обработки ( WSPT ): задания планируются в порядке возрастания соотношения. $p_{j}/w_{j}$ . ^[2]^{: лекция 1, часть 2}

Задача 1|цепи| $\sum w_{j}C_{j}$ является обобщением описанной выше проблемы для заданий с зависимостями в виде цепочек. Ее также можно оптимально решить с помощью подходящего обобщения WSPT. ^[2]^{: лекция 1, часть 3}

Минимизация стоимости опозданий

Проблема 1|| $L_{\max }$ стремится минимизировать максимальную задержку . Для каждого задания j существует срок выполнения. $d_{j}$ . Если задание завершено после установленного срока, оно имеет задержку, определяемую как $L_{j}:=C_{j}-d_{j}$ . 1|| $L_{\max }$ может быть оптимально решено с помощью правила «Сначала самый ранний срок выполнения» ( EDD ): задания планируются в порядке возрастания их крайнего срока. $d_{j}$ . ^[2]^{: лекция 2, часть 2}

Проблема 1|prec| $h_{\max }$ обобщает 1|| $L_{\max }$ двумя способами: во-первых, он допускает произвольные ограничения приоритета заданий; во-вторых, он позволяет каждому заданию иметь произвольную функцию стоимости hj _, которая является функцией времени его завершения (опоздание — это частный случай функции стоимости). Максимальную стоимость можно минимизировать с помощью жадного алгоритма, известного как алгоритм Лоулера . ^[2]^{: лекция 2, часть 1}

Проблема 1 | $r_{j}$ | $L_{\max }$ обобщает 1|| $L_{\max }$ позволяя каждому заданию иметь разное время выпуска , к которому оно становится доступным для обработки. Наличие времени выпуска означает, что в некоторых случаях может оказаться оптимальным оставить машину бездействующей, чтобы дождаться важного задания, которое еще не выпущено. Минимизировать максимальную задержку в этом параметре NP-сложно. Но на практике ее можно решить с помощью алгоритма ветвей и границ . ^[2]^{: лекция 2, часть 3}

Максимизация прибыли от своевременности

В настройках со сроками возможно, что, если работа будет завершена к сроку, будет получена прибыль p _j . В противном случае прибыли нет. Цель – максимизировать прибыль. Планирование с указанием сроков для одной машины является NP-сложным; Сахни ^[3] представлены как точные алгоритмы с экспоненциальным временем, так и алгоритм аппроксимации с полиномиальным временем.

Максимизация пропускной способности

Проблема 1|| $\sum U_{j}$ направлена на минимизацию количества опозданий на работу, независимо от количества опозданий. Оптимально ее можно решить с помощью алгоритма Ходжсона-Мура. ^[4]^[2]^{: лекция 3, часть 1} Это также можно интерпретировать как максимизацию количества работ, выполняемых вовремя; это число называется пропускной способностью .

Проблема 1|| $\sum w_{j}U_{j}$ направлен на минимизацию бремени опозданий на работу. Это NP-трудно, поскольку это особый случай, когда все задания имеют одинаковый срок (обозначается 1| $d_{j}=d$ | $\sum w_{j}U_{j}$ ) эквивалентно задаче о рюкзаке . ^[2]^{: лекция 3, часть 2}

Проблема 1 | $r_{j}$ | $\sum U_{j}$ обобщает 1|| $\sum U_{j}$ позволяя различным заданиям иметь разное время выпуска . Проблема NP-сложная. Однако, когда длины всех заданий равны, проблему можно решить за полиномиальное время. Имеет несколько вариантов:

Вариант взвешенной оптимизации, 1| $r_{j},p_{j}=p$ | $\sum w_{j}U_{j}$ , можно решить за время $O(n^{7})$ . ^[5]
Невзвешенный вариант оптимизации, максимизирующий количество заданий, завершающихся вовремя, обозначается 1 | $r_{j},p_{j}=p$ | $\sum U_{j}$ , можно решить за время $O(n^{5})$ с использованием динамического программирования, когда все сроки и сроки выпуска являются целыми числами. ^[6]^[7]
Вариант решения - решение о том, возможно ли выполнение всех заданных заданий вовремя - может быть решен несколькими алгоритмами: ^[8] самый быстрый из них бежит вовремя $O(n\log n)$ . ^[9]

Задания могут иметь интервалы выполнения . Для каждого задания j существует время обработки t _j и время начала s _j , поэтому оно должно выполняться в интервале [ s _j , s _j +t _j ]. Поскольку некоторые интервалы перекрываются, не все работы могут быть выполнены. Цель — максимизировать количество выполненных заданий, то есть пропускную способность . В более общем смысле, каждое задание может иметь несколько возможных интервалов, и каждый интервал может быть связан с различной прибылью. Цель состоит в том, чтобы выбрать не более одного интервала для каждого задания, чтобы общая прибыль была максимальной. Более подробную информацию можно найти на странице планирования интервалов .

В более общем смысле, задания могут иметь временные окна со временем начала и крайними сроками, которые могут превышать продолжительность задания. Каждое задание можно запланировать в любом месте в пределах своего временного окна. Бар-Ной, Бар-Иегуда, Фройнд, Наор и Шибер ^[10] представим приближение (1- ε )/2.

Работы с непостоянной длиной

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

Продолжительность задания может зависеть от времени начала задания. ^[11] Когда длина является слабо возрастающей функцией времени начала, это эффект ухудшения ; когда он слабо убывает, это называется эффектом обучения .
Длина задания может зависеть от суммы обычного времени обработки ранее обработанных заданий. Когда длина является слабо возрастающей функцией этой суммы, ее часто называют эффектом старения . ^[12]

Длина на основе времени начала

Ченг и Дин изучали минимизацию времени выполнения и минимизацию максимальной задержки, когда фактическая длина задания j, запланированного на момент времени s _j, определяется выражением

${\widehat {p_{j}}}(s_{j})=p_{j}-b\cdot s_{j}$ , где p _j — нормальная длина j .

Они доказали следующие результаты:

Когда задания могут иметь произвольные сроки, проблемы становятся строго NP-сложными за счет сокращения с 3-раздельных ; ^[13]
Когда задания могут иметь один из двух крайних сроков, проблемы являются NP-полными за счет сокращения из раздела . ^[14]
Когда задания могут иметь произвольные сроки выпуска, проблемы становятся строго NP-сложными за счет уменьшения проблемы с произвольными сроками выполнения. ^[15]
Когда задания могут иметь одно из двух времен выпуска: 0 или R, проблемы являются NP-полными. ^[15]

Кубяк и ван-де-Вельде ^[16] изучали минимизацию продолжительности рабочего времени, когда утомление начинается только после обычного срока родов d . То есть фактическая длина задания j, запланированного на момент времени s _j, определяется выражением

${\widehat {p_{j}}}(s_{j})=\max(p_{j},p_{j}+b_{j}\cdot (s_{j}-d))$ .

Итак, если задание начинается до d , его длина не изменится; если он начинается после d , его длина увеличивается в зависимости от задания. Они показывают, что задача NP-трудна, дают псевдополиномиальный алгоритм, работающий во времени. $O(nd\sum _{j}p_{j})$ и предоставить алгоритм ветвей и границ, который решает примеры с количеством заданий до 100 за разумное время. Они также изучают ограниченное ухудшение, когда p _j перестает расти, если работа начинается после общей даты максимального ухудшения D > d. Для этого случая они предлагают два алгоритма с псевдополиномиальным временем.

Ченг, Дин и Линь ^[11] проанализировали несколько исследований эффекта ухудшения, в которых продолжительность задания j, запланированного на момент времени s _j, является либо линейной, либо кусочно-линейной, а скорость изменения может быть положительной или отрицательной.

Длина, основанная на сумме времени обработки

Эффект старения бывает двух типов:

В модели старения на основе позиций время обработки задания зависит от количества заданий, обработанных до него, то есть от его положения в последовательности. ^[17]
В модели старения, основанной на сумме времени обработки , время обработки задания является слабо возрастающей функцией суммы нормального (= незатронутого старением) времени обработки заданий, обработанных до него. ^[18]

Деньги, деньги, деньги и деньги ^[19] Изучена модель старения на основе суммы времени обработки, где время обработки задания j, запланированного в позиции v, определяется выражением

${\widehat {p_{j}}}(\pi ,v)=p_{j}\cdot \left(1+\sum _{l=1}^{v-1}p_{\pi (l)}\right)^{\alpha }$

где $\pi (l)$ запланирована ли работа на позиции $l$ , а α — «характеристика старения» машины. В этой модели максимальное время обработки перестановки $\pi$ является:

$\sum _{l=1}^{n}{\widehat {p_{\pi (l)}}}(\pi ,l)$

Рудек ^[20] обобщил модель двумя способами: позволяя усталости отличаться от времени обработки и допуская характеристику старения, зависящую от работы:

${\widehat {p_{j}}}(\pi ,v)=p_{j}\cdot \left(1+\sum _{l=1}^{v-1}f(p_{\pi (l)})\right)^{\alpha _{j}}$

Здесь f — возрастающая функция, описывающая зависимость усталости от времени обработки; и α _j — характеристика старения работы j . Для этой модели он доказал следующие результаты:

Минимизация максимального времени завершения и минимизация максимальной задержки решаются за полиномиальное время.
Минимизация максимального времени завершения и минимизация максимальной задержки являются строго NP-сложной задачей, если у некоторых заданий есть крайние сроки.

См. также

Интервальное планирование

Многие методы решения были применены для решения задач планирования одной машины. Некоторые из них перечислены ниже.

Ссылки

^ Юджин Л. Лоулер, Ян Карел Ленстра, Александр Х. Г. Риннуй Кан, Дэвид Б. Шмойс (1 января 1993 г.). «Глава 9. Последовательность и планирование: алгоритмы и сложность» . Справочники по исследованию операций и науке управления . 4 : 445–522. дои : 10.1016/S0927-0507(05)80189-6 . ISBN 9780444874726 . ISSN 0927-0507 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Гриншпун, Таль (2020). «Предметы планирования» . www.youtube.com . Проверено 12 сентября 2021 г.
^ Сахни, Сартадж К. (1 января 1976 г.). «Алгоритмы планирования независимых задач» . Журнал АКМ . 23 (1): 116–127. дои : 10.1145/321921.321934 . ISSN 0004-5411 . S2CID 10956951 .
^ Лоулер, Эл. (1 июля 1994 г.). «Задачи планирования, подобные рюкзаку, алгоритм Мура-Ходжсона и свойство «башни множеств»» . Математическое и компьютерное моделирование . 20 (2): 91–106. дои : 10.1016/0895-7177(94)90209-7 . ISSN 0895-7177 .
^ Батист, П. (1999). «Алгоритмы полиномиального времени для минимизации взвешенного количества опоздавших заданий на одной машине с равным временем обработки» . Журнал планирования . 2 (6): 245–252. doi : 10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5 .
^ Хробак, Марек; Дюрр, Кристоф; Явор, Войцех; Ковалик, Лукаш; Куровский, Мачей (1 февраля 2006 г.). «Примечание о планировании заданий одинаковой длины для максимизации пропускной способности» . Журнал планирования . 9 (1): 71–73. arXiv : cs/0410046 . дои : 10.1007/s10951-006-5595-4 . ISSN 1099-1425 . S2CID 7359990 .
^ Хробак, Марек; Дурр, Кристоф; Явор, Войцех; Ковалик, Лукаш; Куровский, Мацей (12 мая 2021 г.). «Примечание о планировании заданий одинаковой длины для максимизации пропускной способности». arXiv : cs/0410046 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Саймонс, Барбара (16 октября 1978 г.). «Быстрый алгоритм однопроцессорного планирования» . Материалы 19-го ежегодного симпозиума по основам информатики . СФКС '78. США: Компьютерное общество IEEE: 246–252. дои : 10.1109/SFCS.1978.4 . S2CID 10284575 .
^ Гэри, MR; Джонсон, Д.С.; Саймонс, Б.Б.; Тарьян, Р.Э. (1 мая 1981 г.). «Планирование задач с произвольным временем выпуска и крайними сроками» . SIAM Journal по вычислительной технике . 10 (2): 256–269. дои : 10.1137/0210018 . ISSN 0097-5397 .
^ Бар-Ной, Амоц; Бар-Иегуда, Реувен; Фройнд, Ари; (Сеффи) Наор, Джозеф; Шибер, Барух (1 сентября 2001 г.). «Единый подход к распределению ресурсов и планированию» . Журнал АКМ . 48 (5): 1069–1090. дои : 10.1145/502102.502107 . ISSN 0004-5411 . S2CID 12329294 .
^ Jump up to: ^а ^б Ченг, TC E; Дин, Кью; Лин, Б.М. Т (1 января 2004 г.). «Краткий обзор планирования с учетом времени обработки, зависящего от времени» . Европейский журнал операционных исследований . 152 (1): 1–13. дои : 10.1016/S0377-2217(02)00909-8 . ISSN 0377-2217 .
^ Чанг, Пей-Чанн; Чен, Ши-Синь; Мани, В. (1 января 2009 г.). «Примечание о назначении сроков выполнения и планировании одной машины с эффектом обучения/старения» . Международный журнал экономики производства . 117 (1): 142–149. дои : 10.1016/j.ijpe.2008.10.004 . ISSN 0925-5273 .
^ Ченг, TCE; Дин, К. (1 июля 1999 г.). «Задача о времени работы машины, зависящая от времени, является строго NP-полной» . Компьютеры и исследования операций . 26 (8): 749–754. дои : 10.1016/S0305-0548(98)00093-8 . ISSN 0305-0548 .
^ Ченг, TCE; Дин, К. (1 июня 1998 г.). «Сложность планирования одной машины с двумя разными крайними сроками и одинаковыми темпами сокращения времени обработки» . Компьютеры и математика с приложениями . 35 (12): 95–100. дои : 10.1016/S0898-1221(98)00099-6 . ISSN 0898-1221 .
^ Jump up to: ^а ^б Ченг, TCE; Дин, К. (29 января 1998 г.). «Сложность планирования запуска задач, зависящих от времени, с учетом времени выпуска» . Письма об обработке информации . 65 (2): 75–79. дои : 10.1016/S0020-0190(97)00195-6 . ISSN 0020-0190 .
^ Кубяк, Веслав; ван де Вельде, Стив (август 1998 г.). «Планирование ухудшающихся работ для минимизации времени ремонта» . Логистика военно-морских исследований . 45 (5): 511–523. doi : 10.1002/(SICI)1520-6750(199808)45:5<511::AID-NAV5>3.0.CO;2-6 . ISSN 0894-069X .
^ Гавейнович, Станислав (25 марта 1996 г.). «Примечание о планировании на одном процессоре со скоростью, зависящей от количества выполняемых заданий» . Письма об обработке информации . 57 (6): 297–300. дои : 10.1016/0020-0190(96)00021-X . ISSN 0020-0190 .
^ Гордон, В.С.; Поттс, Китай; Струсевич В.А.; Уайтхед, доктор юридических наук (1 октября 2008 г.). «Модели планирования одной машины с ухудшением и обучением: обработка ограничений приоритета посредством генерации приоритетов» . Журнал планирования . 11 (5): 357–370. дои : 10.1007/s10951-008-0064-x . ISSN 1099-1425 . S2CID 31422825 .
^ Ван, Цзи-Бо; Ван, Ли-Янь; Ван, Дэн; Ван, Сяо-Юань (1 августа 2009 г.). «Одномашинное планирование с ухудшением, зависящим от времени» . Международный журнал передовых производственных технологий . 43 (7): 805–809. дои : 10.1007/s00170-008-1760-6 . ISSN 1433-3015 . S2CID 110043439 .
^ Рудек, Радослав (01 марта 2012 г.). «Некоторые проблемы планирования на одной машине с расширенным эффектом старения, основанным на сумме времени обработки» . Международный журнал передовых производственных технологий . 59 (1): 299–309. дои : 10.1007/s00170-011-3481-5 . ISSN 1433-3015 .

[:0-1] Юджин Л. Лоулер, Ян Карел Ленстра, Александр Х. Г. Риннуй Кан, Дэвид Б. Шмойс (1 января 1993 г.). «Глава 9. Последовательность и планирование: алгоритмы и сложность» . Справочники по исследованию операций и науке управления . 4 : 445–522. дои : 10.1016/S0927-0507(05)80189-6 . ISBN 9780444874726 . ISSN 0927-0507 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[:1-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Гриншпун, Таль (2020). «Предметы планирования» . www.youtube.com . Проверено 12 сентября 2021 г.

[3] Сахни, Сартадж К. (1 января 1976 г.). «Алгоритмы планирования независимых задач» . Журнал АКМ . 23 (1): 116–127. дои : 10.1145/321921.321934 . ISSN 0004-5411 . S2CID 10956951 .

[4] Лоулер, Эл. (1 июля 1994 г.). «Задачи планирования, подобные рюкзаку, алгоритм Мура-Ходжсона и свойство «башни множеств»» . Математическое и компьютерное моделирование . 20 (2): 91–106. дои : 10.1016/0895-7177(94)90209-7 . ISSN 0895-7177 .

[5] Батист, П. (1999). «Алгоритмы полиномиального времени для минимизации взвешенного количества опоздавших заданий на одной машине с равным временем обработки» . Журнал планирования . 2 (6): 245–252. doi : 10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5 .

[6] Хробак, Марек; Дюрр, Кристоф; Явор, Войцех; Ковалик, Лукаш; Куровский, Мачей (1 февраля 2006 г.). «Примечание о планировании заданий одинаковой длины для максимизации пропускной способности» . Журнал планирования . 9 (1): 71–73. arXiv : cs/0410046 . дои : 10.1007/s10951-006-5595-4 . ISSN 1099-1425 . S2CID 7359990 .

[7] Хробак, Марек; Дурр, Кристоф; Явор, Войцех; Ковалик, Лукаш; Куровский, Мацей (12 мая 2021 г.). «Примечание о планировании заданий одинаковой длины для максимизации пропускной способности». arXiv : cs/0410046 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[8] Саймонс, Барбара (16 октября 1978 г.). «Быстрый алгоритм однопроцессорного планирования» . Материалы 19-го ежегодного симпозиума по основам информатики . СФКС '78. США: Компьютерное общество IEEE: 246–252. дои : 10.1109/SFCS.1978.4 . S2CID 10284575 .

[9] Гэри, MR; Джонсон, Д.С.; Саймонс, Б.Б.; Тарьян, Р.Э. (1 мая 1981 г.). «Планирование задач с произвольным временем выпуска и крайними сроками» . SIAM Journal по вычислительной технике . 10 (2): 256–269. дои : 10.1137/0210018 . ISSN 0097-5397 .

[10] Бар-Ной, Амоц; Бар-Иегуда, Реувен; Фройнд, Ари; (Сеффи) Наор, Джозеф; Шибер, Барух (1 сентября 2001 г.). «Единый подход к распределению ресурсов и планированию» . Журнал АКМ . 48 (5): 1069–1090. дои : 10.1145/502102.502107 . ISSN 0004-5411 . S2CID 12329294 .

[:2-11] Jump up to: ^а ^б Ченг, TC E; Дин, Кью; Лин, Б.М. Т (1 января 2004 г.). «Краткий обзор планирования с учетом времени обработки, зависящего от времени» . Европейский журнал операционных исследований . 152 (1): 1–13. дои : 10.1016/S0377-2217(02)00909-8 . ISSN 0377-2217 .

[12] Чанг, Пей-Чанн; Чен, Ши-Синь; Мани, В. (1 января 2009 г.). «Примечание о назначении сроков выполнения и планировании одной машины с эффектом обучения/старения» . Международный журнал экономики производства . 117 (1): 142–149. дои : 10.1016/j.ijpe.2008.10.004 . ISSN 0925-5273 .

[13] Ченг, TCE; Дин, К. (1 июля 1999 г.). «Задача о времени работы машины, зависящая от времени, является строго NP-полной» . Компьютеры и исследования операций . 26 (8): 749–754. дои : 10.1016/S0305-0548(98)00093-8 . ISSN 0305-0548 .

[14] Ченг, TCE; Дин, К. (1 июня 1998 г.). «Сложность планирования одной машины с двумя разными крайними сроками и одинаковыми темпами сокращения времени обработки» . Компьютеры и математика с приложениями . 35 (12): 95–100. дои : 10.1016/S0898-1221(98)00099-6 . ISSN 0898-1221 .

[:3-15] Jump up to: ^а ^б Ченг, TCE; Дин, К. (29 января 1998 г.). «Сложность планирования запуска задач, зависящих от времени, с учетом времени выпуска» . Письма об обработке информации . 65 (2): 75–79. дои : 10.1016/S0020-0190(97)00195-6 . ISSN 0020-0190 .

[16] Кубяк, Веслав; ван де Вельде, Стив (август 1998 г.). «Планирование ухудшающихся работ для минимизации времени ремонта» . Логистика военно-морских исследований . 45 (5): 511–523. doi : 10.1002/(SICI)1520-6750(199808)45:5<511::AID-NAV5>3.0.CO;2-6 . ISSN 0894-069X .

[17] Гавейнович, Станислав (25 марта 1996 г.). «Примечание о планировании на одном процессоре со скоростью, зависящей от количества выполняемых заданий» . Письма об обработке информации . 57 (6): 297–300. дои : 10.1016/0020-0190(96)00021-X . ISSN 0020-0190 .

[18] Гордон, В.С.; Поттс, Китай; Струсевич В.А.; Уайтхед, доктор юридических наук (1 октября 2008 г.). «Модели планирования одной машины с ухудшением и обучением: обработка ограничений приоритета посредством генерации приоритетов» . Журнал планирования . 11 (5): 357–370. дои : 10.1007/s10951-008-0064-x . ISSN 1099-1425 . S2CID 31422825 .

[19] Ван, Цзи-Бо; Ван, Ли-Янь; Ван, Дэн; Ван, Сяо-Юань (1 августа 2009 г.). «Одномашинное планирование с ухудшением, зависящим от времени» . Международный журнал передовых производственных технологий . 43 (7): 805–809. дои : 10.1007/s00170-008-1760-6 . ISSN 1433-3015 . S2CID 110043439 .

[20] Рудек, Радослав (01 марта 2012 г.). «Некоторые проблемы планирования на одной машине с расширенным эффектом старения, основанным на сумме времени обработки» . Международный журнал передовых производственных технологий . 59 (1): 299–309. дои : 10.1007/s00170-011-3481-5 . ISSN 1433-3015 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

v т и оптимального планирования работы Проблемы
Одноэтапные работы	Одна машина Идентичные машины Униформные машины Несвязанные машины
Многоэтапные работы	Параллельные задачи Открыть магазин Поточный цех Магазин вакансий
Цели оптимизации	Макеспан Ранность Опоздание Опоздание Пропускная способность
Другие требования	Интервальное планирование Правдивое планирование работы