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

Планирование на одной машине или планирование на одном ресурсе или Dhinchak Pooja является задачей оптимизации в информатике и исследовании операций . Нам даны n заданий J 1 , J 2 , ..., J n с различным временем обработки, которые необходимо запланировать на одной машине таким образом, чтобы оптимизировать определенную цель, например, пропускную способность .

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

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

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

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

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

Задача 1|| направлена ​​на минимизацию взвешенной суммы времен завершения. Она может быть решена оптимально с помощью правила Weighted Shortest Processing Time First ( WSPT ): задания планируются в порядке возрастания отношения . [2] : лекция 1, часть 2  ∑ ж дж С дж {\displaystyle \sum w_{j}C_{j}} п дж / ж дж {\displaystyle p_{j}/w_{j}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Продолжительность, основанная на времени начала

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

п дж ^ ( с дж ) = п дж − б ⋅ с дж {\displaystyle {\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] изучали минимизацию makespan, когда усталость начинается только после общей даты выполнения d . То есть фактическая продолжительность работы j, запланированной на время s j, определяется как

п дж ^ ( с дж ) = макс ( п дж , п дж + б дж ⋅ ( с дж − г ) ) {\displaystyle {\widehat {p_{j}}}(s_{j})=\max(p_{j},p_{j}+b_{j}\cdot (s_{j}-d))} .

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

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

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

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

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

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

п дж ^ ( π , в ) = п дж ⋅ ( 1 + ∑ л = 1 в − 1 п π ( л ) ) α {\displaystyle {\widehat {p_{j}}}(\pi ,v)=p_{j}\cdot \left(1+\sum _{l=1}^{v-1}p_{\pi (l)}\right)^{\alpha }}

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

∑ л = 1 н п π ( л ) ^ ( π , л ) {\displaystyle \sum _{l=1}^{n}{\widehat {p_ {\pi (l)}}}(\pi,l)}

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

п дж ^ ( π , в ) = п дж ⋅ ( 1 + ∑ л = 1 в − 1 ф ( п π ( л ) ) ) α дж {\displaystyle {\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-01-01). "Глава 9 Последовательность и планирование: Алгоритмы и сложность". Справочники по исследованию операций и науке управления . 4 : 445– 522. doi :10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN  0927-0507.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  2. ^ abcdefgh Гриншпун, Таль (2020). «Субъекты в планировании». www.youtube.com . Получено 12 сентября 2021 г. .
  3. ^ Сахни, Сартадж К. (1976-01-01). «Алгоритмы планирования независимых задач». Журнал ACM . 23 (1): 116– 127. doi : 10.1145/321921.321934 . ISSN  0004-5411. S2CID  10956951.
  4. ^ Лоулер, Э. Л. (1994-07-01). «Задачи планирования типа рюкзака, алгоритм Мура-Ходжсона и свойство «башни множеств». Математическое и компьютерное моделирование . 20 (2): 91– 106. doi : 10.1016/0895-7177(94)90209-7 . ISSN  0895-7177.
  5. ^ Baptiste, P. (1999). «Алгоритмы полиномиального времени для минимизации взвешенного числа поздних заданий на одной машине с равным временем обработки». Journal of Scheduling . 2 (6): 245– 252. doi :10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5.
  6. ^ Хробак, Марек; Дюрр, Кристоф; Явор, Войцех; Ковалик, Лукаш; Куровский, Мацей (01 февраля 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. ^ Саймонс, Барбара (1978-10-16). "Быстрый алгоритм для планирования одного процессора". Труды 19-го ежегодного симпозиума по основам компьютерной науки . SFCS '78. США: IEEE Computer Society: 246– 252. doi :10.1109/SFCS.1978.4. S2CID  10284575.
  9. ^ Garey, MR; Johnson, DS; Simons, BB; Tarjan, RE (1 мая 1981 г.). «Планирование задач единичного времени с произвольным временем выпуска и крайними сроками». SIAM Journal on Computing . 10 (2): 256– 269. doi :10.1137/0210018. ISSN  0097-5397.
  10. ^ Бар-Ной, Амоц; Бар-Йехуда, Реувен; Фройнд, Ари; (Сеффи) Наор, Джозеф; Шибер, Барух (2001-09-01). «Унифицированный подход к аппроксимации распределения ресурсов и планирования». Журнал ACM . 48 (5): 1069– 1090. doi :10.1145/502102.502107. ISSN  0004-5411. S2CID  12329294.
  11. ^ ab Cheng, TC E; Ding, Q; Lin, BM T (2004-01-01). "Краткий обзор планирования с зависящим от времени временем обработки". European Journal of Operational Research . 152 (1): 1– 13. doi :10.1016/S0377-2217(02)00909-8. ISSN  0377-2217.
  12. ^ Чанг, Пей-Чанн; Чен, Ши-Синь; Мани, В. (01.01.2009). «Заметка о назначении сроков и планировании работы на одной машине с эффектом обучения/старения». Международный журнал экономики производства . 117 (1): 142– 149. doi :10.1016/j.ijpe.2008.10.004. ISSN  0925-5273.
  13. ^ Cheng, TCE; Ding, Q. (1999-07-01). «Задача о времени выполнения машины makespan является строго NP-полной». Computers & Operations Research . 26 (8): 749– 754. doi :10.1016/S0305-0548(98)00093-8. ISSN  0305-0548.
  14. ^ Cheng, TCE; Ding, Q. (1998-06-01). «Сложность планирования работы одной машины с двумя различными крайними сроками и одинаковыми темпами убывания времени обработки». Computers & Mathematics with Applications . 35 (12): 95– 100. doi :10.1016/S0898-1221(98)00099-6. ISSN  0898-1221.
  15. ^ ab Cheng, TCE; Ding, Q. (1998-01-29). «Сложность планирования задач, зависящих от времени начала, с учетом времени выпуска». Information Processing Letters . 65 (2): 75– 79. doi :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. ^ Гавейнович, Станислав (1996-03-25). «Заметка о планировании на одном процессоре со скоростью, зависящей от количества выполняемых заданий». Information Processing Letters . 57 (6): 297– 300. doi :10.1016/0020-0190(96)00021-X. ISSN  0020-0190.
  18. ^ Гордон, В.С.; Поттс, К.Н.; Струсевич, В.А.; Уайтхед, Дж.Д. (2008-10-01). «Модели планирования на одной машине с ухудшением и обучением: обработка ограничений приоритета с помощью генерации приоритетов». Журнал планирования . 11 (5): 357– 370. doi :10.1007/s10951-008-0064-x. ISSN  1099-1425. S2CID  31422825.
  19. ^ Ван, Цзи-Бо; Ван, Ли-Янь; Ван, Дэн; Ван, Сяо-Юань (2009-08-01). «Планирование для одной машины с ухудшением, зависящим от времени». Международный журнал передовых производственных технологий . 43 (7): 805– 809. doi :10.1007/s00170-008-1760-6. ISSN  1433-3015. S2CID  110043439.
  20. ^ Рудек, Радослав (2012-03-01). «Некоторые проблемы планирования для одной машины с расширенным эффектом старения, основанным на сумме времени обработки». Международный журнал передовых производственных технологий . 59 (1): 299– 309. doi : 10.1007/s00170-011-3481-5 . ISSN  1433-3015.
Взято с "https://en.wikipedia.org/w/index.php?title=Планирование_на_одной_машине&oldid=1269340237"