График работы цеха

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

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

В стандартной трехполевой записи задач оптимального планирования работ вариант цеха обозначается буквой J в первом поле. Например, проблема, обозначенная « J3| $p_{ij}$| $C_{\max }$« — это задача цеха с тремя станками и единичным временем обработки, цель которой — минимизировать максимальное время завершения.

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

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

• Машины могут иметь дубликаты (гибкий цех с дублирующими станками) или принадлежать к группам одинаковых станков (гибкий цех).
• Машины могут требовать определенного перерыва между работами или отсутствия простоев.
• Машины могут иметь настройки, зависящие от последовательности.
• Целевая функция может заключаться в минимизации времени обработки, нормы L _p , опозданий, максимального опоздания и т. д. Это также может быть задача многокритериальной оптимизации.
• Задания могут иметь ограничения, например, задание i необходимо завершить, прежде чем задание j можно будет запустить (см. рабочий процесс ). Также целевая функция может быть многокритериальной.
• Набор заданий может относиться к разным наборам машин.
• Детерминированное (фиксированное) время обработки или вероятностное время обработки.

NP-твердость

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

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

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

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

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

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

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

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

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

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

Эффективность

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

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

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

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

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

Основные

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

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

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

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

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

Атомарные задания

См. также: Многопроцессорное планирование.

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

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

Задания, состоящие из нескольких операций

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

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

Смотрите также: правило Джонсона

Эвристический алгоритм С.М. Джонсона можно использовать для решения задачи о работе с двумя машинами N, когда все работы должны обрабатываться в одном и том же порядке. Шаги алгоритма следующие:

Задание Pi _{состоит} из двух операций продолжительностью Pi1 _, Pi2 _, которые должны быть выполнены на машине 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 = sum (время работы на первых m /2 машинах), а время обработки задания P на MC2 = sum (время работы на последних m /2 машинах).

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

Прогноз Makespan

Машинное обучение недавно использовалось для прогнозирования оптимального периода выполнения экземпляра 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} > 0;

param CumulativeTime{i in JOBS, j in MACHINES} =
   sum {jj in MACHINES: ord(jj) <= ord(j)} ProcessingTime[i,jj];

param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <> i2} =
   max {j in MACHINES}
     (CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]);

var end >= 0;
var start{JOBS} >= 0;
var precedes{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)} binary;

minimize makespan: end;

subj to makespan_def{i in JOBS}:
   end >= start[i] + sum{j in MACHINES} ProcessingTime[i,j];

subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   precedes[i1,i2] ==> start[i2] >= start[i1] + TimeOffset[i1,i2];

subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
   !precedes[i1,i2] ==> start[i1] >= start[i2] + TimeOffset[i2,i1];

data;

param N_JOBS := 4;
param N_MACHINES := 4;

param 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-полных задач
• Оптимальное управление
• Планирование (производственные процессы)

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

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