Планирование поточного цеха - Flow shop scheduling

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

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

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

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

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

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

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

(Среднее) Время истечения, ${displaystyle sum (w_ {i}) F_ {i}}$
Макспан, C_{Максимум}
(Среднее) опоздание, ${displaystyle sum (w_ {i}) T_ {i}}$
....

подробное обсуждение измерения производительности можно найти в Малакути (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, p_1i время обработки задания i на машине 1 и p_2i - время обработки задания i на машине 2. Аналогично, p_1j и р_2j время обработки задания j на машине 1 и машине 2 соответственно.
Ниже приведены шаги для алгоритмов Джонсона:
пусть, п_1j= время обработки задания j на машине 1
п_2j= время обработки задания j на машине 2
Алгоритм Джонсона
Шаг 1: сформируйте set1, содержащий все вакансии с p_1j 2j
Шаг 2: форма set2, содержащая все вакансии с p_1j > p_2j, работы с p_1j= p_2j может быть помещен в любой набор.
Шаг 3: Сформируйте последовательность следующим образом:
(i) Задание в set1 идет первым в последовательности, и они идут в порядке возрастания p_1j(SPT)
(ii) Работы в наборе 2 следуют в порядке убывания p_2j (LPT). Связи рвутся произвольно.
Этот тип расписания называется расписанием SPT (1) -LPT (2).

Другие цели

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

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

Сноски

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

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

Тайярд, Э. (январь 1993 г.). «Контрольные показатели для основных задач планирования». Европейский журнал операционных исследований. 64 (2): 278–285. Дои:10.1016 / 0377-2217 (93) 90182-М.
Малакути, Б. (2013). Операционные и производственные системы с несколькими целями. Джон Вили и сыновья. ISBN 978-1-118-58537-5.
Гарей М. Р., Джонсон Д. С. и Сетхи Р. (1976). Сложность планирования потоковых и рабочих мест. Математика исследования операций, 1 (2), 117-129.
Джонсон, С. М. (1954). Оптимальные двух- и трехэтапные производственные графики с учетом времени наладки. Логистика военно-морских исследований ежеквартально, 1 (1), 61-68.

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

Шикарный волк - решатель онлайн-магазинов с визуализацией в реальном времени
Решение проблем с планированием Flowshop

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

[1]