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