Планирование работы Flow-shop

Класс вычислительной задачи

Flow Shop Ордонансмент

Планирование Flow-shop — это задача оптимизации в информатике и исследовании операций . Это вариант оптимального планирования заданий . В общей задаче планирования заданий нам даны n заданий J ₁ ,  J ₂ , ...,  J _n с различным временем обработки, которые необходимо запланировать на m машинах с различной вычислительной мощностью, пытаясь при этом минимизировать makespan — общую длину расписания (то есть время, когда все задания закончат обработку). В конкретном варианте, известном как планирование Flow-shop , каждое задание содержит ровно m операций. i -я операция задания должна быть выполнена на i -й машине. Ни одна машина не может выполнять более одной операции одновременно. Для каждой операции каждого задания указывается время выполнения.

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

В стандартной трехполевой нотации для задач оптимального планирования заданий вариант потокового цеха обозначается как F в первом поле. Например, задача, обозначенная как " F3| | ${\displaystyle p_{ij}}$ ", представляет собой задачу потокового цеха с тремя станками и единичным временем обработки, где целью является минимизация максимального времени завершения. ${\displaystyle C_{\max }}$

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

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

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

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

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

1. (Среднее) Время потока, ${\displaystyle \sum (w_{i})F_{i}}$
2. Makespan, C _макс.
3. (Среднее) Опоздание, ${\displaystyle \sum (w_{i})T_{i}}$
4. ....

Подробное обсуждение измерения производительности можно найти в Malakooti (2013). ^[1]

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

Как было представлено Гари и др. (1976), ^[2] большинство расширений задач планирования потоков-магазинов являются NP-трудными, и лишь немногие из них могут быть решены оптимально за O(nlogn); например, F2|prmu|C _max может быть решена оптимально с использованием правила Джонсона . ^[3]

Тайяр предлагает существенные контрольные задачи для планирования поточных цехов, открытых цехов и цехов по заказу. ^[4]

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

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

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

Задачи 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

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

1. Форма set1, содержащая все задания с p _1j < p _2j
2. Из набора 2, содержащего все задания с p _1j > p _2j , задания с p _1j = p _2j можно поместить в любой из наборов.
3. Сформируйте последовательность следующим образом:

   (i) Работа в set1 идет первой в последовательности, и они идут в порядке возрастания p _1j (SPT)

   (ii) Работы в set2 следуют в порядке убывания p _2j (LPT). Ничьи разрешаются произвольно.

Этот тип расписания называется расписанием SPT(1)–LPT(2).

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

Смотрите также

• График работы открытого цеха
• Планирование работы мастерской

Ссылки

1. Malakooti, ​​B (2013). Операционные и производственные системы с множественными целями. John Wiley & Sons. ISBN  978-1-118-58537-5 .
2. Гари, М. Р.; Джонсон, Д. С.; Сети, Рави (1976). «Сложность планирования Flowshop и Jobshop». Математика исследования операций . 1 (2): 117–129. doi :10.1287/moor.1.2.117.
3. Johnson, SM (1954). «Оптимальные двух- и трехэтапные производственные графики с включенным временем наладки». Naval Research Logistics Quarterly . 1 (1): 61–68. doi :10.1002/nav.3800010110.
4. Taillard, E. (январь 1993). «Тесты для основных задач планирования». European Journal of Operational Research . 64 (2): 278–285. doi :10.1016/0377-2217(93)90182-M.