Планирование магазина Flow

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

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

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

Содержание

  • 1 Формальное определение
  • 2 Измерение производительности секвенирования (γ)
  • 3 Сложность планирования потокового цеха
  • 4 Методы решения
    • 4.1 Минимизация времени изготовления, C max
    • 4.2 Другие цели
  • 5 Сноски
  • 6 Ссылки
  • 7 Внешние ссылки

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

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

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

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

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

  1. (Среднее) Время истечения, ∑ (wi) F i {\ displaystyle \ sum (w_ {i}) F_ {i}}\ sum (w_ {i}) F_ {i}
  2. Makespan, C max
  3. (Среднее) Опоздание, ∑ (wi) T i {\ displaystyle \ sum (w_ {i}) T_ {i}}\ sum (w_ {i}) T_ {i}
  4. ....

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

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

Как представлено Garey et al. (1976), большинство расширений задач планирования потокового цеха являются NP-Hard, и некоторые из них могут быть решены оптимально за O (nlogn), например, F2 | prmu | C max может быть решено оптимально с помощью с использованием правила Джонсона.

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

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

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

F2 | prmu | C max и F3 | prmu | C max можно оптимально решить, используя правило Джонсона (1954), но для общего случая не существует алгоритма, гарантирующего оптимальность решения.. Вот минимизация с использованием правила Джонсона:. Поточный цех содержит n заданий, одновременно доступных в нулевой момент времени и подлежащих обработке двумя машинами, расположенными последовательно с неограниченным хранением между ними. Время обработки всех заданий точно известно. Требуется запланировать n работ на машинах, чтобы минимизировать время изготовления. Правило Джонсона для планирования заданий в цехе с двумя машинами приводится ниже: В оптимальном расписании задание i предшествует заданию j, если min {p 1i,p2j} < min{p1j,p2i}. Где as, p 1i - время обработки задания i на машине 1, а p 2i - время обработки задания i на машине 2. Аналогично, p 1j и p 2j - время обработки задания j на машине 1 и машине 2 соответственно.. Шаги алгоритмов Джонсона суммированы ниже:. let, p 1j = время обработки задания j на машине 1. p2j= время обработки задания j на машине 2. Алгоритм Джонсона. Шаг 1: Форма set1, содержащая все задания с p 1j< p2j. Шаг 2: Форма set2, содержащая все задания с p 1j>p2j, задания с p 1j=p2jмогут быть помещены в любой набор.. Шаг 3: Сформируйте последовательность следующим образом:. (i) Задание в set1 идет первым в последовательности, и они идут в порядке возрастания p 1j (SPT). (ii) Задания в set2 следуют в порядке убывания p 2j (LPT). Связи разрываются произвольно.. Этот тип расписания называется расписанием SPT (1) -LPT (2).

Другие задачи

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

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

Сноски

Ссылки

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

Последняя правка сделана 2021-05-20 09:22:09
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте