Планирование рабочих мест

редактировать

Планирование рабочих мест или проблема рабочих мест (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 NP-твердость
3 Представление проблемы
4 Эффективность планирования
5 Проблема бесконечных затрат
6 Основные результаты
7 Минимизация времени выполнения в автономном режиме
- 7.1 Атомарные задания
- 7.2 Задания, состоящие из нескольких операций
  - 7.2.1 Алгоритм Джонсона
8 Прогнозирование масштаба
9 Пример
10 См. Также
11 Ссылки
12 Внешние ссылки

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

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

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

NP-твердость

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

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

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

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

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

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

x = (1 2 2 3 3 1) {\ displaystyle x = {\ begin {pmatrix} 1 2 \\ 2 3 \\ 3 1 \ end {pmatrix}}}

x = \ begin {pmatrix} 1 2 \\ 2 3 \\ 3 1 \ конец {pmatrix}

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

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

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

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

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

$C ′ = 1 + ∑ i l i ∑ j, k p j k = C. м ∑ J, kpjk {\ displaystyle C '= 1 + {\ sum _ {i} l_ {i} \ over \ sum _ {j, k} p_ {jk}} = {Cm \ over \ sum _ {j, k} p_ {jk}}}$ $C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk}}$

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

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

Одна из первых проблем, которую необходимо решить в JSP, - это то, что многие предлагаемые решения имеют бесконечную стоимость: то есть существует $x ∞ ∈ X {\ displaystyle x _ {\ infty} \ in {\ mathcal {X}}}$ $x _ {\ infty} \ in \ mathcal {X}$ такое, что $C (x ∞) Знак равно + ∞ {\ Displaystyle С (х _ {\ infty}) = + \ infty}$ $C (x _ {\ infty}) = + \ infty$ . Фактически, довольно просто придумать примеры таких $x ∞ {\ displaystyle x _ {\ infty}}$ $x _ {\ infty}$ , убедившись, что две машины будут заблокированы, так что каждая будет ждать для вывода следующего шага другого.

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

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

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

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

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

Минимизация времени выполнения в автономном режиме

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

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

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

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

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

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

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

Задание 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 операций в последовательности, на М1, М2… мм. Мы объединяем первые машины m / 2 в (воображаемый) обрабатывающий центр MC1, а остальные машины в обрабатывающий центр MC2. Тогда общее время обработки для задания P на MC1 = сумма (время работы на первых m / 2 машинах), а время обработки для Job P на MC2 = sum (время обработки на последних m / 2 машинах).

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

Прогноз Makespan

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

Пример

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

параметр N_JOBS; param N_MACHINES; установить JOBS orders = 1..N_JOBS; установить MACHINES orders = 1..N_MACHINES; param ProcessingTime {JOBS, MACHINES}>0; param CumulativeTime {i в ЗАДАНИЯХ, j в МАШИНАХ} = сумма {jj в МАШИНАХ: ord (jj) <= ord(j)} ProcessingTime[i,jj]; param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <>i2} = max {j в МАШИНАХ} (CumulativeTime [i1, j] - CumulativeTime [i2, j] + Время обработки [i2, j]); вар конец>= 0; var start {JOBS}>= 0; var предшествует {i1 в JOBS, i2 в JOBS: ord (i1) < ord(i2)} binary; minimize makespan: end; subj to makespan_def{i in JOBS}: end>= start [i] + sum {j в МАШИНАХ} ProcessingTime [i, j]; subj к no12_conflict {i1 в JOBS, i2 в JOBS: ord (i1) < ord(i2)}: precedes[i1,i2] ==>start [i2]>= start [i1] + TimeOffset [i1, i2]; subj к no21_conflict {i1 в JOBS, i2 в JOBS: ord (i1) < ord(i2)}: !precedes[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;

См. Также

Ссылки

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

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