Планирование работы цеха

Планирование рабочих мест или проблема рабочих мест ( JSP ) - это задача оптимизации в компьютерных науках и исследованиях операций, в которых задания назначаются ресурсам в определенное время. Самая простая версия выглядит следующим образом: нам дается n заданий J ₁ , J ₂ , ..., J _n с различным временем обработки, которые необходимо запланировать на m машинах с различной вычислительной мощностью, пытаясь минимизировать время выполнения . Продолжительность изготовления - это общая длина расписания (то есть, когда все задания закончили обработку).

Стандартная версия задачи - это когда у вас есть n работ J ₁ , J ₂ , ..., J _n . В каждом задании есть набор операций O ₁ , O ₂ , ..., O _n, которые необходимо обрабатывать в определенном порядке (известном как ограничения приоритета). У каждой операции есть конкретный компьютер, на котором она должна выполняться, и только одна операция в задании может быть обработана в данный момент времени. Обычное ослабление - это гибкий цех, где каждая операция может быть обработана на любом станке из заданного набора (станки в наборе идентичны).

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

Первоначально название произошло от планирования заданий в мастерской по трудоустройству , но тема имеет широкое применение за пределами этого типа.

Систематическая нотация была введена для представления различных вариантов этой задачи планирования и связанных с ней проблем, названных трехполевой нотацией .

Варианты проблемы [ править ]

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

Машины могут иметь дубликаты (гибкий цех с дублирующими машинами) или принадлежать к группам одинаковых машин (гибкий цех) ^[3]
Машины могут требовать определенного промежутка времени между заданиями или отсутствия простоев
Машины могут иметь настройки, зависящие от последовательности
Целевая функция может заключаться в минимизации времени изготовления, нормы L _p , опозданий, максимального опоздания и т. Д. Это также может быть многокритериальная задача оптимизации.
Задания могут иметь ограничения, например задание, которое мне нужно завершить, прежде чем задание 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 М_ {я}}$ ${\ displaystyle \ displaystyle J_ {j}}$

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

{\ 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 М_ {я}}$ ${\ displaystyle \ displaystyle J_ {j}}$

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

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

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

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

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

Проблема бесконечной стоимости [ править ]

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

Основные результаты [ править ]

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

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

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

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

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

Минимизация времени автономной работы [ править ]

Атомарные вакансии [ править ]

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

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

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

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

Алгоритм Джонсона [ править ]

Эвристический алгоритм С.М. Джонсона может быть использован для решения задачи задачи с 2 машинами 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 машинах), а время обработки для Job P на MC2 = sum (время работы на последних m / 2 машинах).

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

Прогноз Makespan [ править ]

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

Пример [ править ]

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

param  N_JOBS ; параметр  N_MACHINES ;Набор  ТРУД заказал = 1 .. N_JOBS ; установить МАШИНЫ заказанные = 1 .. N_MACHINES ;       param  ProcessingTime { JOBS ,  MACHINES } > 0 ;  param  CumulativeTime { i в ЗАДАНИЯХ , j в МАШИНАХ } = sum { jj в МАШИНАХ : ord ( jj ) <= ord ( j )} Время обработки [ i , jj ];              параметр  TimeOffset { i1 в ЗАДАНИЯХ , i2 в ЗАДАНИЯХ : i1 <> i2 } = max { j в МАШИНАХ } ( CumulativeTime [ i1 , j ] - CumulativeTime [ i2 , j ] + ProcessingTime [ i2 , j ]);                  var  end > = 0 ; var start { JOBS } > = 0 ; var предшествует { i1 в JOBS , i2 в JOBS : ord ( i1 ) < ord ( i2 )} двоичный ;               минимизировать время  изготовления : конец ; subj в  makepan_def { i в JOBS }: end > = start [ i ] + sum { j in 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 в ЗАДАНИЯХ , i2 в ЗАДАНИЯХ : ord ( i1 ) < ord ( i2 )} :! предшествует [ i1 , i2 ] ==> start [ i1 ] > = start [ i2 ] + TimeOffset [ i2 , i1 ];               данные ;параметр  N_JOBS : = 4 ; параметр N_MACHINES : = 4 ;     param  ProcessingTime : 1 2 3 4 : = 1 4 2 1 2 3 6 2 3 7 2 3 4 1 5 8 ;

См. Также [ править ]

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

Ссылки [ править ]

^ a b Грэм, Р. (1966). «Границы некоторых аномалий многопроцессорной обработки» (PDF) . Технический журнал Bell System . 45 (9): 1563–1581. DOI : 10.1002 / j.1538-7305.1966.tb01709.x .
^ "Taillard Instances" .
^ Маккарти (1993). «Устранение пробелов в планировании исследований: обзор методов оптимизации и эвристики в планировании производства».
^ Malakooti, B (2013). Операционные и производственные системы с множеством целей . Джон Вили и сыновья. ISBN 978-1-118-58537-5.
^ Б. Рой, Б. Суссманн, Les problèmes d'ordonnancement avec constraintes disjonctives, SEMA, Note DS, No. 9, Paris, 1964.
^ Яцек Блажевич, Эрвин Пеш, Малгожата Стерна, Представление дизъюнктивного графового автомата задачи планирования работы цеха, Европейский журнал операционных исследований, том 127, выпуск 2, 1 декабря 2000 г., страницы 317-331, ISSN 0377-2217, 10.1016 / S0377-2217 (99) 00486-5.
^ a b Миршекарян, Садех; Шормаз, Душан Н. (2016). «Взаимосвязь характеристик задачи планирования работы цеха с эффективностью планирования» (PDF) . Экспертные системы с приложениями . 62 : 131–147. DOI : 10.1016 / j.eswa.2016.06.014 .
^ Коффман, EG младший ; Грэхем, Р. Л. (1972), "Оптимальное планирование для систем двух процессоров" (PDF) , Acta , обработка данных , 1 (3): 200-213, DOI : 10.1007 / bf00288685 , МР 0334913 , S2CID 40603807 .
^ Лам, Шуй; Сетхи, Рави (1977), " В худшем случае анализ двух алгоритмов планирования", SIAM журнал по вычислениям , 6 (3): 518-536, DOI : 10,1137 / 0206037 , МР 0496614 .
^ Bartal, Y .; A. Fiat; Х. Карлофф; Р. Вохра (1992). «Новые алгоритмы для древней задачи планирования». Proc. 24-й ACM Symp . Теория вычислений. С. 51–58. DOI : 10.1145 / 129712.129718 .
^ Каргер, Д .; С. Филлипс; Э. Торнг (1994). «Лучший алгоритм для древней задачи планирования» . Proc. Пятый симпозиум ACM . Дискретные алгоритмы.
^ Альберс, Сюзанна ; Торбен Хагеруп (1992). «Улучшена параллельная сортировка целых чисел без одновременной записи» . Труды третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Архив симпозиума по дискретным алгоритмам. С. 463–472.
^ Флейшер, Рудольф (2000). Алгоритмы - ESA 2000 . Берлин / Гейдельберг: Springer. С. 202–210. DOI : 10.1007 / 3-540-45253-2_19 . ISBN 978-3-540-41004-1.
Перейти ↑ Albers, Susanne (1999). «Лучшие границы для онлайн-планирования». SIAM Journal on Computing . 29 (2): 459–473. CiteSeerX 10.1.1.685.8756 . DOI : 10,1137 / S0097539797324874 .
^ Garey, MR (1976). «Сложность планирования Flowshop и Jobshop». Математика исследования операций . 1 (2): 117–129. DOI : 10.1287 / moor.1.2.117 . JSTOR 3689278 .
^ Чен, Синь; Лан, Ян; Бенко, Аттила; Доса, Дьёрдь; Хань, Синь (2011). « Оптимальные алгоритмы онлайн-планирования с ограниченной перестановкой в конце » . Теоретическая информатика . 412 (45): 6269–6278. DOI : 10.1016 / j.tcs.2011.07.014 .
^ Лю, М .; Xu, Y .; Chu, C .; Чжэн, Ф. (2009). «Онлайн-планирование на двух одинаковых машинах для минимизации времени изготовления». Теорет. Comput. Sci . 410 (21–23): 2099–2109. DOI : 10.1016 / j.tcs.2009.01.007 .
^ Хохбаум, Дорит ; Шмойс, Давид (1987). «Использование алгоритмов двойного приближения для задач планирования: теоретические и практические результаты» (PDF) . Журнал ACM . 34 (1): 144–162. CiteSeerX 10.1.1.125.5753 . DOI : 10.1145 / 7531.7535 . S2CID 9739129 .
^ Хури, Сами; Миряла, Соумья Рао (1999). "Генетические алгоритмы для решения задач планирования открытого цеха". Труды 9-й португальской конференции по искусственному интеллекту: прогресс в области искусственного интеллекта . Лондон: Springer Verlag . CiteSeerX 10.1.1.29.4699 .
^ С. М. Джонсон, Оптимальные двух- и трехэтапные графики производства с включенным временем настройки, Naval Res. Бревно. Кварта. I (1954) 61-68.

Внешние ссылки [ править ]

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

[graham1966-1] Грэм, Р. (1966). «Границы некоторых аномалий многопроцессорной обработки» (PDF) . Технический журнал Bell System . 45 (9): 1563–1581. DOI : 10.1002 / j.1538-7305.1966.tb01709.x .

[TaillardIns-2] "Taillard Instances" .

[3] Маккарти (1993). «Устранение пробелов в планировании исследований: обзор методов оптимизации и эвристики в планировании производства».

[4] Malakooti, B (2013). Операционные и производственные системы с множеством целей . Джон Вили и сыновья. ISBN 978-1-118-58537-5.

[5] Б. Рой, Б. Суссманн, Les problèmes d'ordonnancement avec constraintes disjonctives, SEMA, Note DS, No. 9, Paris, 1964.

[6] Яцек Блажевич, Эрвин Пеш, Малгожата Стерна, Представление дизъюнктивного графового автомата задачи планирования работы цеха, Европейский журнал операционных исследований, том 127, выпуск 2, 1 декабря 2000 г., страницы 317-331, ISSN 0377-2217, 10.1016 / S0377-2217 (99) 00486-5.

[:0-7] Миршекарян, Садех; Шормаз, Душан Н. (2016). «Взаимосвязь характеристик задачи планирования работы цеха с эффективностью планирования» (PDF) . Экспертные системы с приложениями . 62 : 131–147. DOI : 10.1016 / j.eswa.2016.06.014 .

[8] Коффман, EG младший ; Грэхем, Р. Л. (1972), "Оптимальное планирование для систем двух процессоров" (PDF) , Acta , обработка данных , 1 (3): 200-213, DOI : 10.1007 / bf00288685 , МР 0334913 , S2CID 40603807 .

[9] Лам, Шуй; Сетхи, Рави (1977), " В худшем случае анализ двух алгоритмов планирования", SIAM журнал по вычислениям , 6 (3): 518-536, DOI : 10,1137 / 0206037 , МР 0496614 .

[10] Bartal, Y .; A. Fiat; Х. Карлофф; Р. Вохра (1992). «Новые алгоритмы для древней задачи планирования». Proc. 24-й ACM Symp . Теория вычислений. С. 51–58. DOI : 10.1145 / 129712.129718 .

[11] Каргер, Д .; С. Филлипс; Э. Торнг (1994). «Лучший алгоритм для древней задачи планирования» . Proc. Пятый симпозиум 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] Перейти ↑ Albers, Susanne (1999). «Лучшие границы для онлайн-планирования». SIAM Journal on Computing . 29 (2): 459–473. CiteSeerX 10.1.1.685.8756 . DOI : 10,1137 / S0097539797324874 .

[garey1976-15] Garey, MR (1976). «Сложность планирования Flowshop и Jobshop». Математика исследования операций . 1 (2): 117–129. DOI : 10.1287 / moor.1.2.117 . JSTOR 3689278 .

[16] Чен, Синь; Лан, Ян; Бенко, Аттила; Доса, Дьёрдь; Хань, Синь (2011). « Оптимальные алгоритмы онлайн-планирования с ограниченной перестановкой в конце » . Теоретическая информатика . 412 (45): 6269–6278. DOI : 10.1016 / j.tcs.2011.07.014 .

[17] Лю, М .; Xu, Y .; Chu, C .; Чжэн, Ф. (2009). «Онлайн-планирование на двух одинаковых машинах для минимизации времени изготовления». Теорет. Comput. Sci . 410 (21–23): 2099–2109. DOI : 10.1016 / j.tcs.2009.01.007 .

[hs-18] Хохбаум, Дорит ; Шмойс, Давид (1987). «Использование алгоритмов двойного приближения для задач планирования: теоретические и практические результаты» (PDF) . Журнал ACM . 34 (1): 144–162. CiteSeerX 10.1.1.125.5753 . DOI : 10.1145 / 7531.7535 . S2CID 9739129 .

[ossp-ga-19] Хури, Сами; Миряла, Соумья Рао (1999). "Генетические алгоритмы для решения задач планирования открытого цеха". Труды 9-й португальской конференции по искусственному интеллекту: прогресс в области искусственного интеллекта . Лондон: Springer Verlag . CiteSeerX 10.1.1.29.4699 .

[20] С. М. Джонсон, Оптимальные двух- и трехэтапные графики производства с включенным временем настройки, Naval Res. Бревно. Кварта. I (1954) 61-68.

[1]