Задача поиска оптимального расписания одного станка с директивными сроками работ
Автор: Сеничев Константин Николаевич
Журнал: Ученые записки Петрозаводского государственного университета @uchzap-petrsu
Рубрика: Физико-математические науки
Статья в выпуске: 2 (147), 2015 года.
Бесплатный доступ
Представлена задача оптимизации работы одного станка, которая может возникать при расчете оптимального плана работы бумагоделательной машины, гофроагрегата, фанерного пресса или других производственных агрегатов, последовательно и неразрывно выполняющих определенные работы. В случае преждевременного начала работы или ее завершения позже установленного директивного срока на расписание налагается штраф в заданных размерах, пропорциональных величине нарушения срока. Требуется минимизировать сумму штрафных санкций за выполнение всех работ. Также рассмотрены вариации задачи в условиях минимизации общего количества нарушенных директивных сроков, одинаковых значений верхних и нижних штрафных санкций, отсутствия ранних сроков начала выполнения работ. Для решения задачи использованы как базовые метаэвристические алгоритмы, так и предложенный автором комбинированный алгоритм, использующий набор метаэвристик для последовательного улучшения найденного решения. При этом для построения окрестности текущего решения используются операторы инверсии, сдвига в начало, сдвига в конец и сдвига в начало и в конец. В результате комбинированный алгоритм демонстрирует прирост качества найденного решения без изменения порядка вычислительной сложности.
Директивные сроки, оптимальное расписание, метаэвристические методы, комбинированный алгоритм
Короткий адрес: https://sciup.org/14750840
IDR: 14750840
Список литературы Задача поиска оптимального расписания одного станка с директивными сроками работ
- Гладков Л. А., Ку р е й ч и к В. В., Ку р е й ч и к В. М. Генетические алгоритмы: Учеб. пособие. 2-е изд. М.: Физматлит, 2006. 320 с.
- Кузнецов В. А., Сеничев К. Н. Метаэвристики для решения комбинаторных задач: Учеб. пособие. Петрозаводск: Изд-во ПетрГУ, 2012. 40 с.
- Кузнецов В. А., Сеничев К. Н. Использование метаэвристик для решения задач дискретного программирования//Вестник Череповецкого государственного университета (технические науки). 2012. № 4. С. 27-31.
- Кузнецов В. А., Сеничев К. Н. Состав и структура метаэвристик для решения комбинаторных задач//Новые информационные технологии в ЦБП и энергетике: Материалы X Междунар. конф. Петрозаводск: Изд-во ПетрГУ, 2012. С. 34-35.
- МакКоннелл Дж. Основы современных алгоритмов. М.: Техносфера, 2004. 368 с.
- Хачатуров В. Р., Веселовский В. Е., Злотов А. В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. М.: Наука, 2000. 354 с.
- Ballestin F., Leus R. Meta-heuristics for stable scheduling on a single machine//Computer and Operation Research. 2008. № 7. P. 2175-2192.
- Blum C. Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison//ACM Computing Surveys. 2003. № 3. P. 268-308.
- Glover F., Kochenberger G. A. Handbook of Metaheuristics. Springer Science & Business Media, 2003. 556 p.
- Mautor T. Intensification Neighborhoods for Local Search Methods. Essays and Surveys in Metaheuristics. Operation Research Computer Science. Kluwer Acad. Publ., 2001. P. 493-508.
- OR-Library. Weighted tardiness. Available at: http://people. brunel.ac.uk/~mastjjb/jeb/orlib/wtinfo.html
