Описание Области
подробнее…
Постановка задачи
Задача планирования для поточной линии (англ. flow shop scheduling problem или permutation flowshop scheduling) – комбинаторная задача теории расписаний. Задача заключается в минимизации времени последовательной выполнения набора работ (требований, деталей) на станках (машинах).
Дано:
• Набор станков для выполнения работ.
• Набор работ для выполнения на станках.
• Порядок выполнения работ. Сначала работа должна выполняться на первом станке, затем на втором и т.д.
• Время выполнения каждой работы на каждом станке.
Ограничения:
• Станок в каждый момент времени может выполнять только одну работу.
• Не допускаются прерывания при выполнении работ.
Требуется:
Найти последовательность выполнения работ на станках, минимизируя время окончания выполнения последней работы.
кратко
Особенности Объекта
подробнее…
Отличие от объекта FlowShop2MJob – отсутствие установок второго типа, ограничений, связывающих их с установками первого типа.
Схема Объекта
Рисунок. Фрагмент потоковой схемы объекта «с именами»
кратко
Особенности Решения S.FlowShop2MJobWait_SCH_DP38c11.
Особенности Задачи
подробнее…
Время выполнения работ на станках:
Станок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, а выполнения работ равны 0.
Цены операций выполнения работ
Рисунок. Фрагмент формы – стадия, установка, операция, поток
кратко
Исходные данные
подробнее…
Работы, выполняемые на станках
Рисунок. Фрагмент формы – стадия, установка, операция, поток
кратко
Результаты решения
подробнее…
Фрагменты расписания
Рисунок. Фрагмент расписания выполнения операций
Объяснения решения
Рисунок. Фрагмент трассы объяснений хода рассуждений Решателя DP
Размерность задачи и характеристики расчета
Размерность задачи:
Стадий 1, Установок 5, Операций 25, Емкостей 0, Интервалов 38, Переменных 950.
Характеристики расчета:
Частичных решений 37; Полных решений 3; Оптимальных решений 1;
Шагов до 1го полного 122; до наилучшего полного 18953;
Минут до 1го полного 00:00; до наилучшего полного 00:00; до оптимального 00:00;
Решатель операций KS3, сервер Intel Core i5-4570 3,2GHz.
кратко