Jump to content

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

(Перенаправлено из расписания цеха Flow )
Планирование цеха потока

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

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

В стандартной записи с тремя полями для задач оптимального планирования заданий вариант потокового цеха обозначается буквой F в первом поле. Например, проблема, обозначенная « F3| | « — это задача поточного цеха с тремя машинами и единичным временем обработки, цель которой — минимизировать максимальное время завершения.

Формальное определение [ править ]

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

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

Измерения эффективности секвенирования (γ) [ править ]

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

  1. (Среднее) Время истечения,
  2. Продолжительность жизни, C макс.
  3. (Среднее) Опоздание,
  4. ....

Подробное обсуждение измерения производительности можно найти у Малакути (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.

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

  1. Сформируйте set1, содержащий все задания с p 1j < p 2j.
  2. Сформируйте набор2, содержащий все задания с p 1j > p 2j , задания с p 1j = p 2j можно поместить в любой набор.
  3. Сформируйте последовательность следующим образом:
    (i) Задания в наборе 1 идут первыми в последовательности и идут в порядке возрастания p 1j (SPT).
    (ii) Задания в наборе 2 следуют в порядке убывания p 2j (LPT). Связи разрываются произвольно.

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

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

См. также [ править ]

Ссылки [ править ]

  1. ^ Jump up to: Перейти обратно: а б Малакути, Б. (2013). Операции и производственные системы с множеством целей. Джон Уайли и сыновья. ISBN   978-1-118-58537-5 .
  2. ^ Гэри, MR; Джонсон, Д.С.; Сетхи, Рави (1976). «Сложность планирования цехов и цехов». Математика исследования операций . 1 (2): 117–129. дои : 10.1287/moor.1.2.117 .
  3. ^ Jump up to: Перейти обратно: а б Джонсон, С.М. (1954). «Оптимальные двух- и трехэтапные графики производства с учетом времени наладки». Ежеквартальный журнал военно-морских исследований по логистике . 1 (1): 61–68. дои : 10.1002/nav.3800010110 .
  4. ^ Тайлард, Э. (январь 1993 г.). «Эталоны для решения основных задач планирования» . Европейский журнал операционных исследований . 64 (2): 278–285. дои : 10.1016/0377-2217(93)90182-М .


Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 535015bb559220cba3da2a132f32be27__1700718720
URL1:https://arc.ask3.ru/arc/aa/53/27/535015bb559220cba3da2a132f32be27.html
Заголовок, (Title) документа по адресу, URL1:
Flow-shop scheduling - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)