Планирование рабочих мест или проблема рабочих мест ( JSP) - это проблема оптимизации в компьютерных науках и исследованиях операций. Это вариант оптимального планирования работ. В общей задаче планирования заданий нам дается n заданий J 1, J 2,..., J n с различным временем обработки, которые необходимо запланировать на m машинах с различной вычислительной мощностью, при этом пытаясь минимизировать время изготовления - общая длина расписания (то есть, когда все задания закончили обработку). В конкретном варианте, известном как планирование работы в цеху, каждое задание состоит из набора операций O 1, O 2,..., O n, которые необходимо обрабатывать в определенном порядке (известном как ограничения приоритета). У каждой операции есть конкретный компьютер, на котором она должна выполняться, и только одна операция в задании может быть обработана в данный момент времени. Обычное ослабление - это гибкий цех, где каждая операция может быть обработана на любом станке из данного набора (станки в каждом наборе идентичны).
Первоначально название произошло от планирования заданий в мастерской по трудоустройству, но тема имеет широкое применение за пределами этого типа. Эта проблема - одна из наиболее известных задач комбинаторной оптимизации, и она была первой проблемой, для которой Грэм в 1966 году представил конкурентный анализ. Лучшие примеры задач для базовой модели с целевым временем выполнения принадлежат Тайярду.
В стандартной трехпольной нотации для задач оптимального планирования заданий вариант мастерской обозначается буквой J в первом поле. Например, проблема, обозначенная как « J3 | | », представляет собой задачу с тремя машинами и цехом с единичным временем обработки, где цель состоит в том, чтобы минимизировать максимальное время выполнения.
Существует множество разновидностей проблемы, в том числе следующие:
Поскольку задача коммивояжера является NP-сложной, проблема мастерской с установкой, зависящей от последовательности, также является NP-сложной, поскольку TSP является частным случаем JSP с одним заданием (города - это машины, а продавец - работа).
Дизъюнктивной график является одним из самых популярных моделей, используемых для описания рабочих мест магазина проблема планирования экземпляров.
Математическая постановка задачи может быть сделана следующим образом:
Позвольте и быть двумя конечными наборами. На счет промышленного происхождения проблемы, называются машины и называются рабочие места.
Позвольте обозначить множество всех последовательных назначений заданий машинам, так что каждое задание выполняется каждой машиной ровно один раз; элементы могут быть записаны в виде матриц, в столбце которых перечисляются задания, которые машина будет выполнять по порядку. Например, матрица
означает, что машина выполнит три задания по порядку, а машина - по порядку.
Предположим также, что существует некоторая функция стоимости. Функция стоимости может быть интерпретирована как «общее время обработки» и может иметь некоторое выражение в терминах времени, то есть стоимость / время для машины, чтобы выполнить работу.
Задача мастерской по трудоустройству состоит в том, чтобы найти такое распределение работ, которое было бы минимальным, то есть такого, что не было бы.
Эффективность планирования может быть определена для графика через отношение общего времени простоя машины к общему времени обработки, как показано ниже:
Здесь время простоя станка, время изготовления и количество станков. Обратите внимание, что согласно приведенному выше определению эффективность планирования - это просто время изготовления, нормированное на количество машин и общее время обработки. Это позволяет сравнивать использование ресурсов экземплярами JSP разного размера.
Одна из первых проблем, которую необходимо решить в JSP, заключается в том, что многие предлагаемые решения имеют бесконечную стоимость: т. Е. Существуют такие, что. Фактически, довольно просто придумать такие примеры, гарантируя, что две машины зайдут в тупик, так что каждая будет ждать вывода следующего шага другой.
Грэм уже представил алгоритм планирования List в 1966 году, который является (2 - 1 / m) -конкурентным, где m - количество машин. Также было доказано, что планирование списков является оптимальным онлайн-алгоритмом для 2-х и 3-х машин. Алгоритм Коффмэны-Грэхэй (1972) для работ равномерной длины также оптимальный для двух машин, и (2 - 2 / м) -competitive. В 1992 году Бартал, Фиат, Карлофф и Вохра представили алгоритм, способный конкурировать с 1,986. Соревновательный алгоритм 1.945 был представлен Каргером, Филипсом и Торнгом в 1994 году. В 1992 году Альберс представил другой алгоритм, который конкурирует с 1.923. В настоящее время наиболее известным результатом является алгоритм Флейшера и Валя, который достигает конкурентного отношения 1,9201.
Нижняя граница 1,852 была представлена Альберсом. Экземпляры Taillard играют важную роль в разработке расписания работы цеха с целью увеличения продолжительности работы.
В 1976 году Гэри представил доказательство того, что эта задача является NP-полной для mgt; 2, то есть ни одно оптимальное решение не может быть проверено за полиномиальное время для трех или более машин (если P = NP ).
В 2011 году Xin Chen et al. предоставил оптимальные алгоритмы для онлайн-планирования на двух связанных машинах, улучшив предыдущие результаты.
Самая простая форма задачи минимизации рабочего времени в автономном режиме связана с атомарными заданиями, то есть заданиями, которые не подразделяются на несколько операций. Это эквивалентно упаковке нескольких предметов различных размеров в фиксированное количество ящиков, так что максимальный необходимый размер ящика будет как можно меньше. (Если вместо этого количество ящиков должно быть минимизировано, а размер ящика фиксирован, проблема становится другой проблемой, известной как проблема упаковки ящиков. )
Дорит С. Хохбаум и Дэвид Шмойс представили схему полиномиального приближения в 1987 году, которая находит приближенное решение проблемы минимизации времени автономной работы с атомарными заданиями с любой желаемой степенью точности.
Основная форма задачи планирования заданий с несколькими (M) операциями на M машинах, при которой все первые операции должны выполняться на первой машине, все вторые операции - на второй и т. Д., И одна задание не может выполняться параллельно, это известно как проблема планирования потокового цеха. Существуют различные алгоритмы, в том числе генетические.
Эвристический алгоритм С.М. Джонсона может быть использован для решения задачи задачи с 2 машинами N, когда все работы должны обрабатываться в одном порядке. Шаги алгоритма следующие:
Задание P i имеет две операции длительностью P i1, P i2, которые должны быть выполнены на машине M1, M2 в этой последовательности.
Если минимум принадлежит P k1,
Удалить K из списка A; Добавьте K в конец списка L1.
Если минимум принадлежит P k2,
Удалить K из списка A; Добавить K в начало списка L2.
Метод Джонсона оптимально работает только для двух машин. Однако, поскольку он оптимален и его легко вычислить, некоторые исследователи попытались применить его для M машин ( M gt; 2).
Идея заключается в следующем: представьте, что каждое задание требует m операций последовательно на M1, M2… Mm. Мы объединяем первые станки m / 2 в (воображаемый) обрабатывающий центр MC1, а остальные станки в обрабатывающий центр MC2. Тогда общее время обработки для задания P на MC1 = сумма (время работы на первых m / 2 машинах), а время обработки для Job P на MC2 = sum (время работы на последних m / 2 машинах).
Таким образом, мы свели проблему m-Machine к задаче планирования для двух обрабатывающих центров. Мы можем решить эту проблему с помощью метода Джонсона.
Машинное обучение недавно использовалось для прогнозирования оптимального времени создания экземпляра JSP без фактического создания оптимального расписания. Предварительные результаты показывают точность около 80% при применении контролируемых методов машинного обучения для классификации небольших случайно сгенерированных экземпляров JSP на основе их оптимальной эффективности планирования по сравнению со средней.
Вот пример задачи планирования работы цеха, сформулированной в AMPL как задача смешанно-целочисленного программирования с индикаторными ограничениями:
param N_JOBS; param N_MACHINES; set JOBS ordered = 1..N_JOBS; set MACHINES ordered = 1..N_MACHINES; param ProcessingTime{JOBS, MACHINES} gt; 0; param CumulativeTime{i in JOBS, j in MACHINES} = sum {jj in MACHINES: ord(jj) lt;= ord(j)} ProcessingTime[i,jj]; param TimeOffset{i1 in JOBS, i2 in JOBS: i1 lt;gt; i2} = max {j in MACHINES} (CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]); var end gt;= 0; var start{JOBS} gt;= 0; var precedes{i1 in JOBS, i2 in JOBS: ord(i1) lt; ord(i2)} binary; minimize makespan: end; subj to makespan_def{i in JOBS}: end gt;= start[i] + sum{j in MACHINES} ProcessingTime[i,j]; subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) lt; ord(i2)}: precedes[i1,i2] ==gt; start[i2] gt;= start[i1] + TimeOffset[i1,i2]; subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) lt; ord(i2)}: !precedes[i1,i2] ==gt; start[i1] gt;= start[i2] + TimeOffset[i2,i1]; data; param N_JOBS:= 4; param 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;