FlowShopInterrupt2M_SCH_DP38. Станки, поточная линия, с прерываниями, Джонсон. Минимум времени завершения всех работ на двух станках. Календарное планирование. 38 интервалов. Без простоя первого станка. * В процессе оформления.

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

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

Дано:

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

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

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

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

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

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

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

Требуется:

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

кратко

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

Отличие от объекта FlowShop2M – нет требования на отсутствие прерываний работ, соответственно отключено моделирующее его ограничение на длительность непрерывного выполнения операций.

кратко

Рисунок. Общий вид потоковой схемы объекта «с именами»

кратко

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

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

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

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

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

•  Время ожидания выполнения работ для первого станка равно 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_нет_работы». Время остальных операций вычислимо и задано их суммарное время работы. Величина поток – доля равномерного выполнения работы. Цены операций не заданы, таким образом общее время выполнения работ на первом станке явно в критерии не учитывается. Оно опосредовано учитывается исходя из последовательности выполнения работ на станках и критерии минимума общего времени выполнения работ на втором станке.

Второй станок, выполняющий работы

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

Примечание. Ожидание работы у второго станка – операция «Станок2_нет_работы» не ограниченное. Время выполнения работ на станке и для соответствующих операций задано их суммарное и непрерывное время работы. Входящий поток имеет величину равную доли равномерного выполнения работы. Цены операций заданы для отражения общего время выполнения работ в критерии.

Выполненные работы на первом станке, которые ожидают выполнения на втором

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

кратко

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

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

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

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

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

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

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

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

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

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

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

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

кратко