Бионические алгоритмы решения иерархической задачи составления расписания при оперативном планировании производства

Рассмотрена задача составления расписания, которая находит свое применение во многих областях, таких как проектное управление, составление расписаний в учебных заведениях и планирование производства. Практическое использование оптимизационных методов для решения задачи составления расписания существенно осложнено тем, что в реальности постановка задачи неразрывно связана с большой размерностью, сложным производственным процессом и множеством нетривиальных ограничений. Все эти особенности приводят к тому, что трудной задачей является даже поиск допустимого решения, а, следовательно, и к необходимости использования проблемно-ориентированных эвристик для решения задачи за приемлемое время. Стабильность производственного процесса требует тщательного соблюдения всех ограничений, но в то же время оперативное планирование производства сопряжено с необходимостью быстрого нахождения решения при любом изменении состояния. Предложено использовать иерархическую структуру, где на верхнем уровне располагается задача коммивояжера, а вложенная задача планирования проекта с ограниченными ресурсами заменена имитационной моделью. Рассмотрено применение таких алгоритмов, как эвристика Лина --- Кернигана, генетический алгоритм и алгоритм муравьиных колоний. Исследована эффективность применения перечисленных алгоритмов при решении задачи составления расписания в предложенной постановке

Литература

[1] Leon A. Enterprise resource planning. McGraw-Hill, 2008.

[2] SAP ERP. Построение эффективной системы управления. М., Альпина Бизнес Букс, 2008.

[3] Пажинская А.А. ERP-системы, их назначение и особенности. Обзор программного обеспечения Microsoft Dynamics. Молодежный научно-технический вестник, 2015, № 3. URL: http://ainsnt.ru/doc/770644.html

[4] Грачева Е.В., Пчелинцева О.Н. Планирование и управление производством предприятий на основе системы Oracle E-Business Suite. Известия ПГПУ им. В.Г. Белинского, 2011, № 26, с. 547–549.

[5] Адуева Т.В., Ахаев А.В., Ходашинский И.А. Продукционная система выбора программных продуктов системы "1С:Предприятие 8". Бизнес-информатика, 2012, № 1 (19), с. 55–61.

[6] Фролов Е.Б., Загидуллин Р.Р. MES-системы как они есть или эволюция систем планирования производства. Станочный парк, 2008, № 10 (55), с. 31–37.

[7] Городецкая О.Ю., Гобарева Я.Л. CRM-система как стратегия управления бизнесом компании. Транспортное дело России, 2014, № 4, с. 169–172.

[8] Джуха В.М., Кириллов Д.О. Потенциальные преимущества APS-систем в продажах и операционном планировании. Управление экономическими системами, 2013, № 7 (55), с. 19.

[9] Идзиковский В.И., Горшкова Е.А. ЛИМС --- автоматизированная система управления для лаборатории, или нечто большее? Современная лабораторная практика, 2012, № 3 (19), с. 10–24.

[10] Амбарцумян А.А., Хадеев А.С. Анализ функциональности систем управления техническим обслуживанием и ремонтом оборудования. Проблемы управления, 2005, № 6, с. 2–12.

[11] Моргунова О.В. Формирование единого информационного пространства предприятия. Сб. тр. X Всерос. науч.-практ. конф. "Математические модели современных экономических процессов, методы анализа и синтеза экономических механизмов. Актуальные проблемы и перспективы менеджмента организаций в России". Самара, СамНЦ РАН, 2015, с. 130–139.

[12] Симонова С.И. Интеллектуальный анализ данных для задач CRM. INJOIT, 2015, № 2, с. 17–22.

[13] Gantt H.L. A graphical daily balance in manufacture. Trans. ASME, 1903, vol. 24, pp. 1322–1336.

[14] Wilson J.M. Gantt charts: a centenary appreciation. EJOR, 2003, vol. 149, iss. 2, pp. 430–437. DOI: 10.1016/S0377-2217(02)00769-5

[15] Аничкин А.С., Семенов В.А. Современные модели и методы теории расписаний. Труды ИСП РАН, 2014, т. 26, № 3, с. 5–50.

[16] Davendra D., ed. Traveling salesman problem. Theory and applications. InTech, 2010.

[17] Blazewicz J., Lenstra J., Rinnooy Kan A.H.G. Scheduling subject to resource constraints: classification and complexity. Discrete Appl. Math., 1983, vol. 5, iss. 1, pp. 11–24. DOI: 10.1016/0166-218X(83)90012-4

[18] Eiben A.E., Smith J.E. Introduction to evolutionary computing. Natural Computing Series. Berlin, Heidelberg, Springer, 2003. DOI: https://doi.org/10.1007/978-3-662-05094-1

[19] Громов С.А., Тарасов В.Б. Интегрированные интеллектуальные системы оперативного планирования производства. Известия ЮФУ. Технические науки, 2011, № 7, с. 60–67.

[20] Скобцов Ю.А., Ченгарь О.В., Скаковская А.Н. Многокритериальный муравьиный алгоритм оптимизации производственного расписания. Математические методы в технике и технологиях, 2016, № 12 (94), с. 245–253.

[21] Papadimitriou C.H., Steiglitz K. Combinatorial optimization. Algorithms and complexity. Prentice-Hall, 1982.

[22] Lin S., Kernigan B.W. An effective heuristic algorithm for the traveling-salesman problem. Oper. Res., 1973, vol. 21, no. 2, pp. 498–516.

[23] Holland J.H. Adaptation in natural and artificial systems. The University of Michigan Press, 1975.

[24] Dorigo М., Gambardella L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput., 1997, vol. 1, no. 1, pp. 53–66. DOI: 10.1109/4235.585892

[25] Семенкина О.Е., Семенкина О.Э. Исследование эффективности бионических алгоритмов комбинаторной оптимизации. Программные продукты и системы, 2013, № 3, c. 23.

[26] Семенкина О.Е. Сравнение эффективности муравьиного и генетического алгоритмов при решении задач комбинаторной оптимизации. Вестник СибГАУ, 2012, № 4 (44), c. 96–98.

[27] Semenkina O., Ryzhikov I., Semenkin E. The large-scale optimization problem of product distribution in orders. Proc. 5th Int. Workshop Math. Models Appl. (IWMMA). Krasnoyarsk, Russia, 2017, pp. 126–134.

[28] Semenkina O.Ev., Popov E.A., Semenkina O.Er. Self-conjuring nature inspired algorithms for combinatorial optimization problems. Журнал Сибирского федерального университета. Серия: Математика и физика, 2017, т. 10, № 4, с. 463–473.

[29] Семенкина О.Е., Попов Е.А., Семенкина О.Э. Self-configuring evolutionary algorithms for travelling salesman problem. Вестник СибГАУ, 2013, № 4 (50), с. 134–139.