Планирование поточного цеха
Планирование потокового цеха — это задача оптимизации в информатике и исследовании операций . Это вариант оптимального планирования работы . В общей задаче планирования заданий нам даны n заданий J 1 , J 2 , ..., J n с различным временем обработки, которые необходимо запланировать на m машинах с различной вычислительной мощностью, пытаясь при этом минимизировать время выполнения : общая продолжительность расписания (то есть время, когда все задания завершили обработку). В конкретном варианте, известном как планирование потокового цеха , каждое задание содержит ровно m операций. -я операция i задания должна быть выполнена на i -й машине. Ни одна машина не может выполнять более одной операции одновременно. Для каждой операции каждого задания указывается время выполнения.
Потоковое планирование — это особый случай планирования цеха , при котором существует строгий порядок выполнения всех операций на всех заданиях. Поточное планирование может применяться как к производственным объектам, так и к компьютерным проектам. Особым типом задачи потокового планирования является задача перестановочного потокового планирования , в которой порядок обработки заданий на ресурсах одинаков для каждого последующего шага обработки.
В стандартной записи с тремя полями для задач оптимального планирования заданий вариант потокового цеха обозначается буквой F в первом поле. Например, проблема, обозначенная « F3| | « — это задача поточного цеха с тремя машинами и единичным временем обработки, цель которой — минимизировать максимальное время завершения.
Формальное определение [ править ]
Имеется m машин и n рабочих мест. Каждое задание содержит ровно m операций. -я операция i задания должна быть выполнена на i -й машине. Ни одна машина не может выполнять более одной операции одновременно. Для каждой операции каждого задания указывается время выполнения.
Операции в рамках одного задания должны выполняться в указанном порядке. Первая операция выполняется на первой машине, затем (по завершении первой операции) вторая операция на второй машине и так далее до m -й операции. Однако задания могут выполняться в любом порядке. Определение задачи подразумевает, что этот порядок работ одинаков для каждой машины. Проблема состоит в том, чтобы определить оптимальную такую схему, т. е. ту, которая имеет минимально возможную общую продолжительность выполнения работы.
Измерения эффективности секвенирования (γ) [ править ]
Задачу секвенирования можно сформулировать как определение последовательности S, позволяющей оптимизировать одну или несколько целей секвенирования.
- (Среднее) Время истечения,
- Продолжительность жизни, C макс.
- (Среднее) Опоздание,
- ....
Подробное обсуждение измерения производительности можно найти у Малакути (2013). [1]
потокового планирования Сложность цеха
Как представлено Гари и др. (1976), [2] большинство расширений задач планирования потоков и цехов являются NP-сложными, и лишь немногие из них могут быть решены оптимально за O(nlogn); например, F2|prmu|C max можно оптимально решить с помощью правила Джонсона . [3]
Тайллар предлагает существенные контрольные задачи для планирования поточных цехов, открытых цехов и цехов. [4]
Методы решения [ править ]
Предложенные методы решения задач планирования потоков и цехов можно классифицировать как точные алгоритмы, такие как метод ветвей и границ , и эвристические алгоритмы , такие как генетический алгоритм .
Минимизация продолжительности рабочего цикла, C max [ править ]
F2|prmu|C max и F3|prmu|C max можно оптимально решить с помощью правила Джонсона. [3] но для общего случая не существует алгоритма, гарантирующего оптимальность решения.
Поточный цех содержит n заданий, одновременно доступных в нулевой момент времени и обрабатываемых двумя машинами, расположенными последовательно, с неограниченным объемом памяти между ними. Время обработки всех заданий достоверно известно. Необходимо запланировать n заданий на машинах так, чтобы минимизировать время простоя. Ниже приведено правило Джонсона для планирования работ в двухмашинном поточном цехе.
В оптимальном расписании задание i предшествует заданию j, если min{p 1i ,p 2j } < min{p 1j ,p 2i } . Где p 1i — это время обработки задания i на машине 1, а p 2i — это время обработки задания i на машине 2. Аналогично, p 1j и p 2j — это время обработки задания j на машине 1 и машине 2 соответственно.
Для алгоритма Джонсона:
- Пусть p 1j — время обработки задания j на машине 1.
- и p 2j время обработки задания j на машине 2.
Алгоритм Джонсона:
- Сформируйте set1, содержащий все задания с p 1j < p 2j.
- Сформируйте набор2, содержащий все задания с p 1j > p 2j , задания с p 1j = p 2j можно поместить в любой набор.
- Сформируйте последовательность следующим образом:
- (i) Задания в наборе 1 идут первыми в последовательности и идут в порядке возрастания p 1j (SPT).
- (ii) Задания в наборе 2 следуют в порядке убывания p 2j (LPT). Связи разрываются произвольно.
Расписание этого типа называется расписанием SPT(1)–LPT(2).
Подробное обсуждение доступных методов решения представлено Малакути (2013). [1]
См. также [ править ]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б Малакути, Б. (2013). Операции и производственные системы с множеством целей. Джон Уайли и сыновья. ISBN 978-1-118-58537-5 .
- ^ Гэри, MR; Джонсон, Д.С.; Сетхи, Рави (1976). «Сложность планирования цехов и цехов». Математика исследования операций . 1 (2): 117–129. дои : 10.1287/moor.1.2.117 .
- ^ Jump up to: Перейти обратно: а б Джонсон, С.М. (1954). «Оптимальные двух- и трехэтапные графики производства с учетом времени наладки». Ежеквартальный журнал военно-морских исследований по логистике . 1 (1): 61–68. дои : 10.1002/nav.3800010110 .
- ^ Тайлард, Э. (январь 1993 г.). «Эталоны для решения основных задач планирования» . Европейский журнал операционных исследований . 64 (2): 278–285. дои : 10.1016/0377-2217(93)90182-М .