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

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

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

Дано:

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

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

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

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

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

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

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

Требуется:

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

кратко

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

Установки первого типа отражают работы, которые выполняются на станках.

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

Число установок второго типа соответствует числу станков – 2, последовательно выполняющих работы.

Установки второго типа отражают занятость станков и используются для определения момента окончания выполнения всех работ на станке.

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

кратко

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

кратко

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

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

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

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

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

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

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

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

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

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

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

Связь между выполнением работ и занятостью станка задается ограничениями на обязательную работу и паузу в интервале времени

Ограничения на операции, связывающие выполнение работ и станки:

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

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

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

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

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

Изменяя условия и постановку задачи был введен дополнительный критерий – минимум суммарного времени ожидания выполнения всех работ. Используется критерий «Переключение». Стоимости переходов на операции ожидания выполнения работ, как с выполнения работы на предыдущем станке, так и продолжение ожидания равны 1. Остальные допустимые переходы равны 0. Этот критерий имеет меньший приоритет по сравнению с основным и ориентирован на увеличение скорости расчета.

Цены переналадок для работ

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

кратко

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

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

Станки, использующиеся для выполнения работ

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

кратко

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

Выполнение работ

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

Выполнение работ

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

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

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

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

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

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

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

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

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

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

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

кратко