WikiDer > Планирование поточного цеха

Flow shop scheduling

Планирование поточного цеха проблемы, это класс планирование проблемы с цех в котором управление потоком должно обеспечивать соответствующую последовательность для каждого задания и для обработки в наборе машины или с другими Ресурсы 1,2, ..., м в соответствии с заданными порядками обработки. Особенно желательно поддержание непрерывного потока задач обработки с минимумом время простоя и минимум время ожидания. Планирование поточного цеха - это частный случай планирование работы цеха где есть строгий порядок выполнения всех операций над всеми работами. Планирование поточного цеха может также применяться к производство возможности в отношении вычисление конструкции.

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

Формальное определение

Есть п машины и м рабочие места. Каждая работа содержит ровно п операции. В я-я операция задания должна выполняться на я-й автомат. Ни одна машина не может выполнять более одной операции одновременно. Для каждой операции каждого задания указывается время выполнения.

Операции в рамках одного задания должны выполняться в указанном порядке. Первая операция выполняется на первой машине, затем (по завершении первой операции) вторая операция на второй машине и так далее, пока п-я операция. Однако задания можно выполнять в любом порядке. Определение проблемы подразумевает, что этот порядок работы одинаков для каждой машины. Проблема состоит в том, чтобы определить оптимальную такую ​​схему, то есть такую, при которой общая продолжительность выполнения задания минимальна.[1]

Измерения производительности секвенирования (γ)

Задача секвенирования может быть сформулирована как определение последовательности S, при которой оптимизируется одна или несколько целей секвенирования.

  1. (Среднее) Время истечения,
  2. Макспан, CМаксимум
  3. (Среднее) опоздание,
  4. ....

подробное обсуждение измерения производительности можно найти в Малакути(2013).

Сложность планирования потокового цеха

Как представлено Garey et al. (1976), большинство расширений задач планирования потокового цеха NP-Hard, и некоторые из них могут быть решены оптимально за O (nlogn), например F2 | prmu | CМаксимум можно оптимально решить, используя Правило Джонсона.

Методы решения

Предлагаемые методы решения задач планирования потокового цеха можно классифицировать как точный алгоритм такие как Ветвь и граница и Эвристический алгоритм такие как генетический алгоритм.

Минимизация времени приготовления, CМаксимум

F2 | prmu | CМаксимум и F3 | prmu | CМаксимум можно оптимально решить, используя Правило Джонсона (1954), но для общего случая не существует алгоритма, гарантирующего оптимальность решения.
Вот минимизация с использованием правила Джонсона:
Поточный цех содержит n заданий, доступных одновременно в нулевой момент времени и подлежащих обработке двумя последовательно расположенными машинами с неограниченным хранением между ними. Время обработки всех заказов точно известно. Требуется запланировать n работ на машинах, чтобы минимизировать время изготовления. Правило Джонсона для планирования заданий в цехе с двумя потоками машин приведено ниже: В оптимальном расписании задание i предшествует заданию j, если мин {р1i,п2j} 1j,п2i}. Где as, p1i время обработки задания i на машине 1 и p2i - время обработки задания i на машине 2. Аналогично, p1j и р2j время обработки задания j на машине 1 и машине 2 соответственно.
Ниже приведены шаги для алгоритмов Джонсона:
пусть, п1j= время обработки задания j на машине 1
п2j= время обработки задания j на машине 2
Алгоритм Джонсона
Шаг 1: сформируйте set1, содержащий все вакансии с p1j 2j
Шаг 2: форма set2, содержащая все вакансии с p1j > p2j, работы с p1j= p2j может быть помещен в любой набор.
Шаг 3: Сформируйте последовательность следующим образом:
(i) Задание в set1 идет первым в последовательности, и они идут в порядке возрастания p1j(SPT)
(ii) Работы в наборе 2 следуют в порядке убывания p2j (LPT). Связи рвутся произвольно.
Этот тип расписания называется расписанием SPT (1) -LPT (2).

Другие цели

Алгоритм оптимален.

Подробное обсуждение доступных методов решения предоставлено Малакути (2013).

Сноски

  1. ^ "шикарный сайт". Получено 28 декабря 2015.

использованная литература

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