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

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

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

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

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

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

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

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

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

1. (Среднее) Время истечения, ${displaystyle sum (w_ {i}) F_ {i}}$
2. Макспан, C_{Максимум}
3. (Среднее) опоздание, ${displaystyle sum (w_ {i}) T_ {i}}$
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, 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).

Сноски

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

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

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