ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ

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

1.Kostenko V.A. Scheduling algorithms for real-time computing systems admitting simulation models // Programming and Computer Software. 2013. V. 39. N 5. P. 255–267. doi: 10.1134/S0361768813050034

2.Kostenko V.A., Vinokurov A.V. Locally optimal algorithms for designing schedules based on Hopfield networks // Programming and Computer Software. 2003. V. 29. N 4. P. 199–209. doi: 10.1023/A:1024918625291

3.Гончаров Е.Н. Стохастический жадный алгоритм для задачи календарного планирования с ограниченными ресурсами // Дискретный анализ и исследование операций. 2014. Т. 21. № 3. С. 11–24.

4.Еремеев А.В., Коваленко Ю.В. О сложности оптимальной рекомбинации для одной задачи составления расписаний с переналадками // Дискретный анализ и исследование операций. 2012. Т. 19. № 3. С. 13–26.

5.Великанова Ю.Ю. Оценки времени работы алгоритмов локального спуска для задачи построения расписаний на параллельных машинах // Дискретный анализ и исследование операций. 2012. Т. 19. № 5. С. 21–34.

6.Воронин А.В., Кузнецов В.А., Шабаев А.И., Архипов И.В., Кашевник А.М. Разработка и реализация системы планирования лесопильным производством // Труды СПИИРАН. 2012. №4 (23). С. 400–415.

7.Voronin A.V., Kuznetsov V.A., Arkhipov I.V., Shabaev A.I. Software system for sawmill operation planning // Proc. 12^th Conference of FRUCT Association. St. Petersburg, Russia, 2012. P. 165–171.

8.Shabaev A.I., Arhipov I.V., Spirichev M.V., Urban A.R., Torozerov M.A. Development of planning system for plywood production using matrix designer // Proc. 14^th Conference of Open Innovation Association, FRUCT. Espoo, Finland, 2013. P. 140–147. doi: 10.1109/FRUCT.2013.6737956

9.Архипов И.В. Математические модели раскроя лесосырья в задачах планирования и управления лесопильным производством // Ученые записки ПетрГУ. Серия: естественные и технические науки. 2013. № 8 (137). С 93–97.

10.Архипов И. В. Математические модели и опыт реализации системы планирования раскроя лесосырья // Вестник СПбГУ. Серия 10. Прикладная математика. Информатика. Процессы управления. 2014. № 3. С. 82–92.

11.Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. М.: Физматлит, 2002. 176 с.

12.Урбан А.Р., Кузнецов В.А. Математические модели и методы учета сроков продукции в задаче раскроя тамбуров бумагоделательных машин // Ученые записки ПетрГУ. Серия: естественныеитехническиенауки. 2014. № 4 (141). С. 112–115.

13.Урбан А.Р. Решение задачи поиска оптимального столбца в условиях оптимального раскроя бумажного полотна // Вестник СПбГУ. Серия 10. Прикладная математика. Информатика. Процессы управления. 2015. № 1. С. 100–106.

14.Афанасьева А.С., Буздалов М.В. Выбор функции приспособленности особей генетического алгоритма с помощью обучения с подкреплением // Научно-технический вестник информационных технологий, механики и оптики. 2012. № 1 (77). С. 77–81.

15.Степанов Д.В., Шалыто А.А. Использование генетического алгоритма для поиска оптимальной траектории наблюдателя // Научно-технический вестник информационных технологий, механики и оптики. 2012. № 1 (77). С. 90–95.

16.Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: Регулярная и хаотическая динамика, 2001. 288 с.

17.Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. 2-еизд. М.: Вильямс, 2005. 1296 с.

18.Vasenin V.A., Vodomerov A.N. A formal model of a system for automated program parallelization // Programming and Computer Software. 2007. V. 33. N 4. P. 181–194. doi: 10.1134/S0361768807040019

19.Kalenkova A.A. An algorithm of automatic workflow optimization // Programming and Computer Software. 2012. V. 38. N 1. P. 43–56. doi: 10.1134/S0361768812010045

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License