Планирование рабочих мест или проблема рабочих мест ( JSP ) - это задача оптимизации в компьютерных науках и исследованиях операций, в которых задания назначаются ресурсам в определенное время. Самая простая версия выглядит следующим образом: нам дается n заданий J 1 , J 2 , ..., J n с различным временем обработки, которые необходимо запланировать на m машинах с различной вычислительной мощностью, пытаясь минимизировать время выполнения . Продолжительность изготовления - это общая длина расписания (то есть, когда все задания закончили обработку).
Стандартная версия задачи - это когда у вас есть n работ J 1 , J 2 , ..., J n . В каждом задании есть набор операций O 1 , O 2 , ..., O n, которые необходимо обрабатывать в определенном порядке (известном как ограничения приоритета). У каждой операции есть конкретный компьютер, на котором она должна выполняться, и только одна операция в задании может быть обработана в данный момент времени. Обычное ослабление - это гибкий цех, где каждая операция может быть обработана на любом станке из заданного набора (станки в наборе идентичны).
Эта проблема - одна из наиболее известных задач комбинаторной оптимизации , и она была первой проблемой, для которой конкурентный анализ был представлен Грэхемом в 1966 году. [1] Лучшие примеры задач для базовой модели с целевым временем выполнения принадлежат Тайярду. [2]
Первоначально название произошло от планирования заданий в мастерской по трудоустройству , но тема имеет широкое применение за пределами этого типа.
Систематическая нотация была введена для представления различных вариантов этой задачи планирования и связанных с ней проблем, названных трехполевой нотацией .
Варианты проблемы
Существует множество разновидностей проблемы, в том числе следующие:
- Машины могут иметь дубликаты (гибкий цех с дублирующими машинами) или принадлежать к группам одинаковых машин (гибкий цех) [3]
- Машины могут требовать определенного промежутка времени между заданиями или отсутствия простоев
- Машины могут иметь настройки, зависящие от последовательности
- Целевая функция может заключаться в минимизации времени изготовления, нормы L p , опозданий, максимального опоздания и т. Д. Это также может быть многокритериальная задача оптимизации.
- Задания могут иметь ограничения, например задание, которое мне нужно завершить, прежде чем задание j может быть запущено (см. Рабочий процесс ). Также целевая функция может быть многокритериальной. [4]
- Набор заданий может относиться к разному набору машин.
- Детерминированное (фиксированное) время обработки или вероятностное время обработки
NP-твердость
Поскольку задача коммивояжера является NP-трудной , проблема работы магазин с установкой последовательности в зависимости от явно также NP-трудной , поскольку TSP является частным случаем JSP с одного задания (города являются машины и продавец является работа). [ необходима цитата ]
Представление проблемы
Дизъюнктивной граф [5] является одним из самых популярных моделей , используемых для описания работы магазина проблема планирования экземпляров. [6]
Математическая постановка задачи может быть сделана следующим образом:
Позволять а также - два конечных множества . Из-за промышленного происхождения проблемыназываются машинами, аназываются рабочими местами .
Позволять обозначить множество всех последовательных назначений заданий машинам, так что каждое задание выполняется каждой машиной ровно один раз; элементы можно записать как матрицы, в которых столбец перечисляет задания, которые машина сделаю, по порядку. Например, матрица
означает, что машина выполнит три работы в порядке , в то время как машина выполню работу в порядке .
Предположим также, что существует некоторая функция стоимости . Функция стоимости может быть интерпретирована как «общее время обработки» и может иметь некоторое выражение в единицах времени., стоимость / время для машины делать работу .
Задача job-shop - найти задание на работу. такой, что минимум, то есть нет такой, что .
Эффективность планирования
Эффективность планирования может быть определена для графика через отношение общего времени простоя машины к общему времени обработки, как показано ниже:
Здесь время простоя машины , это время приготовления и количество машин. Обратите внимание, что согласно приведенному выше определению эффективность планирования - это просто время изготовления, нормированное на количество машин и общее время обработки. Это позволяет сравнивать использование ресурсов экземплярами JSP разного размера. [7]
Проблема бесконечной стоимости
Одна из первых проблем, которые необходимо решить в JSP, заключается в том, что многие предлагаемые решения имеют бесконечную стоимость: т. Е. Существует такой, что . На самом деле, придумать примеры такихгарантируя, что две машины зайдут в тупик , чтобы каждая из них ожидала вывода следующего шага другой.
Основные результаты
Грэм уже представил алгоритм планирования 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 to 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 .
- ^ «Подземелья Тайярда» .
- ^ Маккарти (1993). «Устранение пробелов в планировании исследований: обзор методов оптимизации и эвристики в планировании производства».
- ^ Малакути, Б. (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.
- ^ а б Миршекарян, Садех; Шормаз, Душан Н. (2016). «Взаимосвязь характеристик задачи планирования работы цеха с эффективностью планирования» (PDF) . Экспертные системы с приложениями . 62 : 131–147. DOI : 10.1016 / j.eswa.2016.06.014 .
- ^ Коффман, EG Jr .; Грэхем, Р. Л. (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.
- ^ Альберс, Сюзанна (1999). «Лучшие границы для онлайн-планирования». SIAM Journal on Computing . 29 (2): 459–473. CiteSeerX 10.1.1.685.8756 . DOI : 10,1137 / S0097539797324874 .
- ^ Гарей, 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
- Визуальное планирование работы магазина