FlowShop2MJobWait_SCH_DP38c12. Станки, поточная линия, без прерываний, Джонсон. Минимум времени ожидания при выполнении работ на двух станках. Календарное планирование. 38 интервалов. Cтоимости простоя 1го станка — 1, 2го — 2.

Постановка задачи

Задача планирования для поточной линии (англ. flow shop scheduling problem или permutation flowshop scheduling) – комбинаторная задача теории расписаний. Задача заключается в минимизации времени последовательной выполнения набора работ (требований, деталей) на станках (машинах).

Дано:

•  Набор станков для выполнения работ.

•  Набор работ для выполнения на станках.

•  Порядок выполнения работ. Сначала работа должна выполняться на первом станке, затем на втором и т.д.

•  Время выполнения каждой работы на каждом станке.

Ограничения:

•  Станок в каждый момент времени может выполнять только одну работу.

•  Не допускаются прерывания при выполнении работ.

Требуется:

Найти последовательность выполнения работ на станках, минимизируя время окончания выполнения последней работы.

кратко

См. Объект FlowShop2MJob. Задача Джонсона о станках, поточная линия. Минимум времени последовательного выполнения всех работ на двух станках.

Отличие от объекта FlowShop2MJob – отсутствие установок второго типа, ограничений, связывающих их с установками первого типа.

Схема Объекта

Рисунок. Фрагмент потоковой схемы объекта «с именами»

кратко

Время выполнения работ на станках:

Станок1: Работа1 – 5 часов, Работа2 – 2 часа, Работа3 – 3 часа, Работа4 – 6 часов, Работа5 – 7 часов;

Станок2: Работа1 – 1 час, Работа2 – 4 часа, Работа3 – 3 часа, Работа4 – 5 часов, Работа5 – 2 часа;

Число интервалов времени избыточно и равно суммарному времени поочередного выполнения работ на каждом станке – самый худший вариант.

Требование последовательного выполнения работ задается ограничениями на длительность работы/паузы одной операции от начала/конца другой. Стадии выполнения работ строго упорядочены: ожидание выполнения на первом станке (если есть), выполнение на первом станке, ожидание выполнения на втором (если есть) и т.д.

Заданная последовательность выполнения каждой работы:

Рисунок. Фрагмент формы – Ограничения на длительность работы/паузы одной операции от начала/конца другой

Требование отсутствия прерывания при обработке задается ограничениями на длительность непрерывного выполнения – операция выполняется непрерывно, все необходимое время.

Требование единовременного выполнения на станке только одной работы учитывается ограничением на альтернативность для всех операций выполнения работ на одном станке в интервале времени.

Альтернативное выполнение работ на одном станке:

Рисунок. Фрагмент формы – Ограничения на работу операций в интервале времени

Не изменяя условия и постановку исходной задачи для ускорения поиска решения были введены дополнительные ограничения:

•  Время ожидания выполнения работ для первого станка равно 0. Первый станок выполняет работы без ожидания, для него всегда есть работы для выполнения.

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

Критерий – минимум суммарного времени выполнения всех работ. Используется критерий «Выполнение». Стоимости операций ожидания выполнения работ отличны от нуля, а выполнения работ равны 0.

Критерий изменяет условия и постановку задачи.

Стоимости операций ожидания выполнения работ на первом станке равны 1, ожидания выполнения работ на втором станке равны 2, а выполнения работ равны 0.

Цены операций выполнения работ

Рисунок. Фрагмент формы – стадия, установка, операция, поток

кратко

Работы, выполняемые на станках

Рисунок. Фрагмент формы – стадия, установка, операция, поток

кратко

Фрагменты расписания

Рисунок. Фрагмент расписания выполнения операций

Объяснения решения

Рисунок. Фрагмент трассы объяснений хода рассуждений Решателя DP

Размерность задачи и характеристики расчета

Размерность задачи:

Стадий 1, Установок 5, Операций 25, Емкостей 0, Интервалов 38, Переменных 950.

Характеристики расчета:

Частичных решений 37; Полных решений 2; Оптимальных решений 1;

Шагов до 1го полного 122; до наилучшего полного 9572;

Минут до 1го полного 00:00; до наилучшего полного 00:00; до оптимального 00:00;

Решатель операций KS3, сервер Intel Core i5-4570 3,2GHz.

кратко