Планирование работы мастерской

Проблема оптимизации

Job-shop scheduling , job-shop problem ( JSP ) или job-shop scheduling problem ( JSSP ) — это задача оптимизации в информатике и исследовании операций . Это вариант оптимального планирования заданий . В общей задаче планирования заданий нам даны n заданий J ₁ ,  J ₂ , ...,  J _n с различным временем обработки, которые необходимо запланировать на m машинах с различной вычислительной мощностью, при этом пытаясь минимизировать makespan — общую длину расписания (то есть время, когда все задания закончат обработку). В конкретном варианте, известном как job-shop scheduling , каждое задание состоит из набора операций O ₁ ,  O ₂ , ...,  O _n , которые необходимо обработать в определенном порядке (известном как ограничения очередности ). Каждая операция имеет определенную машину , на которой ее необходимо обработать, и только одна операция в задании может быть обработана в заданное время. Распространенным послаблением является гибкий цех, где каждая операция может быть выполнена на любом станке из заданного набора (станки в каждом наборе идентичны).

Название изначально произошло от планирования работ в магазине , но эта тема имеет широкое применение за пределами этого типа экземпляра. Эта задача является одной из самых известных задач комбинаторной оптимизации и первой задачей, для которой был представлен конкурентный анализ , Грэмом в 1966 году. ^[1] Лучшие примеры задач для базовой модели с целью makespan принадлежат Тайяру. ^[2]

В стандартной трехполевой нотации для задач оптимального планирования заданий вариант job-shop обозначается J в первом поле. Например, задача, обозначенная " ", представляет собой задачу job-shop с тремя станками и единичным временем обработки, где целью является минимизация максимального времени завершения. ${\displaystyle J_{3}|p_{ij}|C_{\max }}$

Варианты решения проблемы

Существует множество вариаций этой проблемы, включая следующие:

• Станки могут иметь дубликаты (гибкий цех с дубликатами станков) или принадлежать к группам идентичных станков (гибкий цех). ^[3]
• Машинам может потребоваться определенный перерыв между заданиями или вообще не требоваться простоя.
• Машины могут иметь настройки, зависящие от последовательности.
• Целевой функцией может быть минимизация времени выполнения заказа, нормы L p , опоздания, максимального опоздания и т. д. Это также может быть задача многокритериальной оптимизации.
• Задания могут иметь ограничения, например, задание i должно быть завершено до того, как задание j может быть начато (см. рабочий процесс ). Кроме того, целевая функция может быть многокритериальной. ^[4]
• Набор работ может относиться к разным наборам машин.
• Детерминированное (фиксированное) время обработки или вероятностное время обработки.

NP-твердость

Поскольку задача коммивояжера является NP-трудной , задача «Магазин-работа» с последовательно-зависимой настройкой, очевидно, также является NP-трудной, поскольку TSP является частным случаем JSP с одной задачей (города — это машины, а продавец — работа). ^{[ необходима цитата ]}

Представление проблемы

Дизъюнктивный граф ^[5] является одной из популярных моделей, используемых для описания примеров задач планирования работ в цехе. ^[6]

Математическая постановка задачи может быть сделана следующим образом:

Пусть и будут двумя конечными множествами . Ввиду промышленного происхождения проблемы называются машинами , а называются рабочими местами . ${\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}}$ ${\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\}}$ ${\displaystyle \displaystyle M_{i}}$ ${\displaystyle \displaystyle J_{j}}$

Пусть обозначает множество всех последовательных назначений работ машинам, так что каждая работа выполняется каждой машиной ровно один раз; элементы могут быть записаны в виде матриц, в столбце которых перечислены работы, которые машина будет выполнять, по порядку. Например, матрица ${\displaystyle \displaystyle \ {\mathcal {X}}}$ ${\displaystyle x\in {\mathcal {X}}}$ ${\displaystyle n\times m}$ ${\displaystyle \displaystyle i}$ ${\displaystyle \displaystyle M_{i}}$

${\displaystyle x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix}}}$

означает, что машина выполнит три работы в указанном порядке , в то время как машина выполнит работы в указанном порядке . ${\displaystyle \displaystyle M_{1}}$ ${\displaystyle \displaystyle J_{1},J_{2},J_{3}}$ ${\displaystyle \displaystyle J_{1},J_{2},J_{3}}$ ${\displaystyle \displaystyle M_{2}}$ ${\displaystyle \displaystyle J_{2},J_{3},J_{1}}$

Предположим также, что есть некоторая функция стоимости . Функция стоимости может быть интерпретирована как «общее время обработки» и может иметь некоторое выражение в терминах времени , стоимости/времени, затрачиваемого машиной на выполнение работы . ${\displaystyle C:{\mathcal {X}}\to [0,+\infty ]}$ ${\displaystyle C_{ij}:M\times J\to [0,+\infty ]}$ ${\displaystyle \displaystyle M_{i}}$ ${\displaystyle \displaystyle J_{j}}$

Задача «магазина работ» состоит в том, чтобы найти такое распределение работ , при котором является минимумом, то есть не существует такого, что . ${\displaystyle x\in {\mathcal {X}}}$ ${\displaystyle \displaystyle C(x)}$ ${\displaystyle y\in {\mathcal {X}}}$ ${\displaystyle \displaystyle C(x)>C(y)}$

Эффективность планирования

Эффективность планирования можно определить через отношение общего времени простоя машины к общему времени обработки, как показано ниже:

${\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk}}}$

Здесь — время простоя машины i , C — время выполнения, а m — количество машин. Обратите внимание, что при указанном выше определении эффективность планирования — это просто время выполнения, нормализованное по количеству машин и общему времени обработки. Это позволяет сравнивать использование ресурсов между экземплярами JSP разного размера. ^[7] ${\displaystyle l_{i}}$

Проблема бесконечной стоимости

Одной из первых проблем, с которой необходимо разобраться в JSP, является то, что многие предлагаемые решения имеют бесконечную стоимость: т. е. существует такое, что . На самом деле, довольно просто придумать примеры таких решений , обеспечив тупиковую ситуацию для двух машин , так что каждая из них будет ждать вывода следующего шага другой. ${\displaystyle x_{\infty }\in {\mathcal {X}}}$ ${\displaystyle C(x_{\infty })=+\infty }$ ${\displaystyle x_{\infty }}$

Основные результаты

Грэхем уже представил алгоритм планирования List в 1966 году, который является (2 − 1/ m ) -конкурентным, где m — количество машин. ^[1] Также было доказано, что планирование List является оптимальным онлайн-алгоритмом для 2 и 3 машин. Алгоритм Коффмана–Грэхема (1972) для заданий одинаковой длины также является оптимальным для двух машин и является (2 − 2/ m ) -конкурентным. ^{[8] [9]} В 1992 году Бартал, Фиат, Карлофф и Вохра представили алгоритм, который является 1,986-конкурентным. ^[10] Алгоритм, который является 1,945-конкурентным, был представлен Каргером, Филлипсом и Торнгом в 1994 году. ^[11] В 1992 году Альберс представил другой алгоритм, который является 1,923-конкурентным. ^[12] В настоящее время наиболее известным результатом является алгоритм, предложенный Флейшером и Валем, который достигает конкурентного коэффициента 1,9201. ^[13]

Нижняя граница 1,852 была представлена ​​Альберсом. ^[14] Примеры Тайяра играют важную роль в разработке планирования работ в цехе с целью makespan.

В 1976 году Гэри предоставил доказательство ^[15] , что эта задача является NP-полной для m>2, то есть оптимальное решение не может быть вычислено за детерминированное полиномиальное время для трех или более машин (если только P=NP ).

В 2011 году Синь Чен и др. представили оптимальные алгоритмы для онлайн-планирования на двух связанных машинах ^[16], улучшив предыдущие результаты. ^[17]

Минимизация makespan в автономном режиме

Атомные рабочие места

Простейшая форма проблемы минимизации офлайн makespan имеет дело с атомарными заданиями, то есть заданиями, которые не подразделяются на несколько операций. Это эквивалентно упаковке ряда элементов различных размеров в фиксированное количество контейнеров, так что максимальный необходимый размер контейнера будет как можно меньше. (Если вместо этого число контейнеров должно быть минимизировано, а размер контейнера фиксирован, проблема становится другой проблемой, известной как задача упаковки контейнеров .)

Дорит С. Хохбаум и Дэвид Шмойс представили в 1987 году схему аппроксимации с полиномиальным временем , которая находит приближенное решение задачи минимизации времени выполнения в автономном режиме с атомарными заданиями с любой желаемой степенью точности. ^[18]

Работы, состоящие из нескольких операций

Основная форма задачи планирования заданий с несколькими (M) операциями, на M машинах, так что все первые операции должны быть выполнены на первой машине, все вторые операции на второй и т. д., и одна работа не может быть выполнена параллельно, известна как задача планирования flow-shop . Существуют различные алгоритмы, включая генетические алгоритмы . ^[19]

Алгоритм Джонсона

Эвристический алгоритм SM Johnson может быть использован для решения задачи с двумя машинами N, когда все работы должны быть обработаны в одном и том же порядке. ^[20] Шаги алгоритма следующие:

Работа P _i состоит из двух операций длительностью P _i1 , P _i2 , которые должны быть выполнены на станке M1, M2 в указанной последовательности.

• Шаг 1. Список A = { 1, 2, …, N }, Список L1 = {}, Список L2 = {}.
• Шаг 2. Из всех доступных длительностей операций выберите минимальную.

Если минимум принадлежит P _k1 ,

Удалить K из списка A; Добавить K в конец списка L1.

Если минимум принадлежит P _k2 ,

Удалить K из списка A; Добавить K в начало списка L2.

• Шаг 3. Повторяйте шаг 2, пока список A не опустеет.
• Шаг 4. Соединить список L1, список L2. Это оптимальная последовательность.

Метод Джонсона работает оптимально только для двух машин. Однако, поскольку он оптимален и прост в вычислении, некоторые исследователи пытались адаптировать его для M машин ( M  > 2.)

Идея заключается в следующем: представьте, что каждая работа требует m операций в последовательности на M1, M2 … Mm. Мы объединяем первые m /2 станков в (воображаемый) обрабатывающий центр MC1, а оставшиеся станки в обрабатывающий центр MC2. Тогда общее время обработки для работы P на MC1 = сумма (времена операций на первых m /2 станках), а время обработки для работы P на MC2 = сумма (времена операций на последних m /2 станках).

Сделав это, мы свели задачу m-Machine к задаче планирования двух обрабатывающих центров. Мы можем решить ее с помощью метода Джонсона.

Прогноз Makespan

Машинное обучение недавно использовалось для прогнозирования оптимального периода выполнения экземпляра JSP без фактического создания оптимального расписания. ^[7] Предварительные результаты показывают точность около 80%, когда контролируемые методы машинного обучения применялись для классификации небольших случайно сгенерированных экземпляров JSP на основе их оптимальной эффективности планирования по сравнению со средним значением.

Пример

Вот пример задачи планирования работ по цеху, сформулированной в AMPL как задача программирования со смешанным целым числом и ограничениями по индикаторам:

параметр N_JOBS ; параметр N_MACHINES ;  установить упорядоченные ЗАДАНИЯ = 1 .. N_ЗАДАНИЙ ; установить упорядоченные МАШИНЫ = 1 .. N_МАШИН ;        параметр ProcessingTime { ЗАДАНИЯ , МАШИНЫ } > 0 ;    параметр CumulativeTime { i в JOBS , j в MACHINES } = sum { jj в MACHINES : ord ( jj ) <= ord ( j )} ProcessingTime [ i , jj ];               параметр TimeOffset { i1 в JOBS , i2 в JOBS : i1 <> i2 } = max { j в MACHINES } ( CumulativeTime [ i1 , j ] - CumulativeTime [ i2 , j ] + ProcessingTime [ i2 , j ]);                   вар конец >= 0 ; вар старт { РАБОТЫ } >= 0 ; var предшествует { i1 в JOBS , i2 в JOBS : ord ( i1 ) < ord ( i2 )} двоичный ;                минимизировать makespan : конец ;  subj для makespan_def { i в JOBS }: end >= start [ i ] + sum { j в MACHINES } ProcessingTime [ i , j ];           subj к no12_conflict { i1 в JOBS , i2 в JOBS : ord ( i1 ) < ord ( i2 )}: предшествует [ i1 , i2 ] ==> start [ i2 ] >= start [ i1 ] + TimeOffset [ i1 , i2 ];                subj к no21_conflict { i1 в JOBS , i2 в JOBS : ord ( i1 ) < ord ( i2 )}: ! предшествует [ i1 , i2 ] ==> start [ i1 ] >= start [ i2 ] + TimeOffset [ i2 , i1 ];                данные ;параметр N_JOBS : = 4 ; параметр N_MACHINES : = 4 ;      параметр ProcessingTime : 1 2 3 4 : = 1 5 4 2 1 2 8 3 6 2 3 9 7 2 3 4 3 1 5 8 ;                      

Связанные проблемы

• Планирование работы поточного цеха представляет собой похожую проблему, но без ограничения, что каждая операция должна выполняться на определенном станке (сохраняется только ограничение по порядку).
• Планирование работы в условиях открытого цеха представляет собой похожую проблему, но также без ограничений по заказу.

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

• Дизъюнктивный граф
• Динамическое программирование
• Генетический алгоритм планирования
• Список NP-полных задач
• Оптимальное управление
• Планирование (производственные процессы)

Ссылки

1. Graham, R. (1966). "Границы для некоторых аномалий многопроцессорной обработки" (PDF) . Bell System Technical Journal . 45 (9): 1563–1581. doi :10.1002/j.1538-7305.1966.tb01709.x.
2. «Случаи Тайяра».
3. Маккарти (1993). «Устранение пробела в исследованиях по планированию: обзор методов оптимизации и эвристики в производственном планировании».
4. Малакути, Б. (2013). Операционные и производственные системы с множественными целями . John Wiley & Sons. ISBN 978-1-118-58537-5.
5. Б. Рой, Б. Суссманн, Les problèmes d'ordonnancement avec Constructes Disjonctives, SEMA, Note DS, № 9, Париж, 1964.
6. Яцек Блажевич, Эрвин Пеш, Малгожата Стерна, Представление задачи планирования работ в цехе с помощью дизъюнктивной графовой машины, Европейский журнал операционных исследований, том 127, выпуск 2, 1 декабря 2000 г., страницы 317–331, ISSN 0377-2217, 10.1016/S0377-2217(99)00486-5.
7. Mirshekarian, Sadegh; Šormaz, Dušan N. (2016). «Корреляция особенностей задач планирования работ в цехе с эффективностью планирования» (PDF) . Expert Systems with Applications . 62 : 131–147. doi :10.1016/j.eswa.2016.06.014.
8. Коффман, Э. Г. младший ; Грэм, Р. Л. (1972), «Оптимальное планирование для двухпроцессорных систем» (PDF) , Acta Informatica , 1 (3): 200–213, doi :10.1007/bf00288685, MR  0334913, S2CID  40603807.
9. Лам, Шуй; Сети, Рави (1977), «Анализ наихудшего случая двух алгоритмов планирования», SIAM Journal on Computing , 6 (3): 518–536, doi :10.1137/0206037, MR  0496614.
10. Bartal, Y.; A. Fiat; H. Karloff; R. Vohra (1992). «Новые алгоритмы для древней проблемы планирования». Труды 24-го симпозиума ACM . Теория вычислений. стр. 51–58. doi :10.1145/129712.129718.
11. Каргер, Д .; С. Филлипс; Э. Торнг (1994). «Лучший алгоритм для древней проблемы планирования». Труды Пятого симпозиума ACM . Дискретные алгоритмы.
12. Альберс, Сюзанна ; Торбен Хагеруп (1992). «Улучшенная параллельная сортировка целых чисел без параллельной записи». Труды третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Архив симпозиума по дискретным алгоритмам. стр. 463–472.
13. Флейшер, Рудольф (2000). Алгоритмы – ESA 2000. Берлин / Гейдельберг: Springer. стр. 202–210. doi :10.1007/3-540-45253-2_19. ISBN 978-3-540-41004-1.
14. Альберс, Сюзанна (1999). «Лучшие границы для онлайн-планирования». Журнал SIAM по вычислениям . 29 (2): 459–473. CiteSeerX 10.1.1.685.8756 . doi :10.1137/S0097539797324874. 
15. Garey, MR; Johnson, DS; Sethi, Ravi (1976). «Сложность планирования Flowshop и Jobshop». Математика исследования операций . 1 (2): 117–129. doi :10.1287/moor.1.2.117. JSTOR  3689278.
16. Чен, Синь; Лан, Ян; Бенко, Аттила; Доса, Дьёрдь; Хан, Синь (2011). «Оптимальные алгоритмы онлайн-планирования с ограниченной перестановкой в ​​конце». Теоретическая информатика . 412 (45): 6269–6278. дои : 10.1016/j.tcs.2011.07.014 .
17. Лю, М.; Сюй, И.; Чу, Ч.; Чжэн, Ф. (2009). «Онлайн-планирование на двух однородных машинах для минимизации времени выполнения». Theoret. Comput. Sci . 410 (21–23): 2099–2109. doi : 10.1016/j.tcs.2009.01.007 .
18. Хохбаум, Дорит ; Шмойс, Дэвид (1987). «Использование алгоритмов двойного приближения для задач планирования: теоретические и практические результаты» (PDF) . Журнал ACM . 34 (1): 144–162. CiteSeerX 10.1.1.125.5753 . doi :10.1145/7531.7535. S2CID  9739129. 
19. Хури, Сами; Мирьяла, Соумья Рао (1999). «Генетические алгоритмы для решения задач планирования открытого цеха». Труды 9-й Португальской конференции по искусственному интеллекту: прогресс в области искусственного интеллекта . Лондон: Springer Verlag . CiteSeerX 10.1.1.29.4699 . 
20. SM Johnson, Оптимальные двух- и трехэтапные графики производства с учетом времени наладки, Naval Res. Log. Quart. I (1954) 61-68.

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

• Справочник Венского университета по методологиям, системам и программному обеспечению для динамической оптимизации.
• Примеры Тайяра
• Брукер П. Алгоритмы планирования. Гейдельберг, Шпрингер. Пятое изд. ISBN 978-3-540-24804-0