Описание Области
подробнее…
Постановка задачи
Задача планирования для поточной линии (англ. flow shop scheduling problem или permutation flowshop scheduling) – комбинаторная задача теории расписаний. Задача заключается в минимизации времени последовательной выполнения набора работ (требований, деталей) на станках (машинах).
Дано:
• Набор станков для выполнения работ.
• Набор работ для выполнения на станках.
• Порядок выполнения работ. Сначала работа должна выполняться на первом станке, затем на втором и т.д.
• Время выполнения каждой работы на каждом станке.
Ограничения:
• Станок в каждый момент времени может выполнять только одну работу.
• Не допускаются прерывания при выполнении работ.
Требуется:
Найти последовательность выполнения работ на станках, минимизируя время окончания выполнения последней работы.
кратко
Особенности Объекта
подробнее…
Число установок соответствует числу станков – 2.
Установки отражают выполнение работ на станке. Операциями установок является выполнение одной из 5 работ, ожидание выполнения работы и окончание выполнения всех работ на станке. Потоками операций являются взятая на выполнение работа с прошлого станка и выполненная работа на текущем станке.
Число интервалов времени избыточно и равно суммарному времени поочередного выполнения работ на каждом станке – самый худший вариант.
кратко
Схема Объекта
подробнее…
Рисунок. Общий вид потоковой схемы объекта «с именами»
кратко
Особенности Решения S.FlowShop2M_SCH_DP38.
Особенности Задачи
подробнее…
Требование последовательного выполнения работ задается дискретными потоками величиной 1 для операций выполнения работы на станке. Входящий поток – работа должна быть выполнена на предыдущем станке. Выходящий поток – после выполнения работы она доступна для выполнения на следующем станке.
Требование отсутствия прерывания при выполнении работ задается ограничениями на длительность непрерывного выполнения работы на станке – работа выполняется непрерывно, все необходимое время.
Требование единовременного выполнения только одной работы на станке учитывается альтернативностью операций установок.
Для определения момента окончания выполнения всех работ на станке используется операция окончания выполнения работ на станке. Эта завершающая операция установки. С нее запрещен переход на другие операции, на нее может быть переход только с выполнения одной из работ.
Не изменяя условия и постановку исходной задачи для ускорения поиска решения были введены дополнительные ограничения:
• Время ожидания выполнения работ для первого станка равно 0. Первый станок выполняет работы без ожидания, для него всегда есть работы для выполнения.
• Время выполнения операции окончания выполнения всех работ на станке задано жестко, благодаря имеющимся временам выполнения работ и отсутствию ожидания.
Критерий – минимум времени окончания выполнения последней работы. Для минимизации времени окончания выполнения работ используется критерий «Выполнение». Для этого стоимость операций ожидания и выполнения работ для последнего станка равны 1 – счетчик времени, затраченного на выполнение работ, а стоимость окончания выполнения всех работ равна 0 – время на выполнение работ не затрачивается.
Время выполнения работ на станках:
Станок1: Работа1 – 5 часов, Работа2 – 2 часа, Работа3 – 3 часа, Работа4 – 6 часов, Работа5 – 7 часов;
Станок2: Работа1 – 1 час, Работа2 – 4 часа, Работа3 – 3 часа, Работа4 – 5 часов, Работа5 – 2 часа;
кратко
Исходные данные
подробнее…
Первый станок, выполняющий работы
Рисунок. Фрагмент формы – стадия, установка, операция, поток
Примечание. Отсутствует ожидание работы у первого станка – операция «Станок1_нет_работы». Время остальных операций вычислимо и задано их суммарное и непрерывное время работы. Дискретный поток величиной 1 гарантирует начало работы второго станка после окончания работы первого. Цены операций не заданы, таким образом общее время выполнения работ на первом станке явно в критерии не учитывается. Оно опосредовано учитывается исходя из последовательности выполнения работ на станках и критерии минимума общего времени выполнения работ на втором станке.
Второй станок, выполняющий работы
Рисунок. Фрагмент формы – стадия, установка, операция, поток
Примечание. Ожидание работы у второго станка – операция «Станок2_нет_работы» не ограниченное. Время выполнения работ на станке и для соответствующих операций задано их суммарное и непрерывное время работы. Входящий дискретный поток величиной 1 гарантирует начало работы второго станка после окончания работы первого. Цены операций заданы для отражения общего время выполнения работ в критерии.
Выполненные работы на первом станке, которые ожидают выполнения на втором
Рисунок. Фрагменты формы – стадия, емкость
кратко
Результаты решения
подробнее…
Фрагменты расписания
Рисунок. Фрагмент расписания выполнения операций
Объяснения решения
Рисунок. Фрагмент трассы объяснений хода рассуждений Решателя DP
Размерность задачи и характеристики расчета
Размерность задачи:
Стадий 2, Установок 2, Операций 14, Емкостей 5, Интервалов 38, Переменных 532.
Характеристики расчета:
Частичных решений 50; Полных решений 2; Оптимальных решений 1;
Шагов до 1го полного 112; до наилучшего полного 32031;
Минут до 1го полного 00:00; до наилучшего полного 00:00; до оптимального 00:00;
Решатель операций KS3, сервер Intel Core i5-4570 3,2GHz.
кратко