Иерархический самоконфигурируемый алгоритм кооперативной коэволюции для решения задачи составления расписания

Аннотация

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

Работа выполнена в соответствии с государственным заданием Минобрнауки России (№ FEFE-2023-0004)

Просьба ссылаться на эту статью следующим образом:

Семенкина О.Е., Становов В.В., Попов Е.А. Иерархический самоконфигурируемый алгоритм кооперативной коэволюции для решения задачи составления расписания. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2023, № 4 (145), с. 131--148. DOI: https://doi.org/10.18698/0236-3933-2023-4-131-148

Литература

[1] Oztemel E., Gursev S. Literature review of Industry 4.0 and related technologies. J. Intell. Manuf., 2020, vol. 31, no. 4, pp. 127--182. DOI: https://doi.org/10.1007/s10845-018-1433-8

[2] Li Y., Goga K., Tadei R., et al. Production scheduling in Industry 4.0. CISIS 2020. Cham, Springer Nature, 2020, pp. 355--364. DOI: https://doi.org/10.1007/978-3-030-50454-0_34

[3] Шевляков А.О., Матвеев М.Г. Решение RCPSP при нечетких трудозатратах выполнения операций. Вестник ВГУ. Сер. Системный анализ и информационные технологии, 2015, № 4, с. 121--125.

[4] Zaman F., Elsayed S.M., Sarker R.A., et al. Scenario-based solution approach for uncertain resource constrained scheduling problems. IEEE CEC, 2018. DOI: https://doi.org/10.1109/CEC.2018.8477756

[5] Chakrabortty R.K., Sarker R.A., Essam D.L. Resource constrained project scheduling with uncertain activity durations. Comput. Ind. Eng., 2017, vol. 112, pp. 537--550. DOI: https://doi.org/10.1016/j.cie.2016.12.040

[6] Creemers S. Minimizing the expected makespan of a project with stochastic activity durations under resource constraints. J. Sched., 2015, vol. 18, no. 3, pp. 263--273. DOI: https://doi.org/10.1007/s10951-015-0421-5

[7] Calmels D. The job sequencing and tool switching problem: state-of-the-art literature review, classification, and trends. Int. J. Prod. Res., 2019, vol. 57, no. 15-16, pp. 5005--5025. DOI: https://doi.org/10.1080/00207543.2018.1505057

[8] Семенкина О.Е., Рыжиков И.С., Липинский Л.В. и др. Метод моделирования производственных систем для оперативного планирования производства. Системы управления и информационные технологии, 2021, № 3, с. 17--24.

[9] Семенкина О.Е. Кооперативная коэволюция самоконфигурируемых бионических алгоритмов в задачах составления расписания. Системы управления и информационные технологии, 2022, № 1, с. 63--68.

[10] Аничкин А.С., Семенов В.А. Современные модели и методы теории расписаний. Труды Института системного программирования РАН, 2014, т. 26, № 3, с. 5--50. DOI: https://doi.org/10.15514/ISPRAS-2014-26(3)-1

[11] Liu Y., Wang L., Wang X., et al. Scheduling in cloud manufacturing: state-of-the-art and research challenges. Int. J. Prod. Res., 2019, vol. 57, no. 15-16, pp. 4854--4879. DOI: https://doi.org/10.1080/00207543.2018.1449978

[12] Back T., Fogel D.B., Michalewicz Z., eds. Handbook of evolutionary computation. Oxford, Oxford University Press, 1997.

[13] Bansal J.C. Particle swarm optimization. Evolutionary and swarm intelligence algorithms. Cham, Springer Nature, 2019, pp. 11--23. DOI: https://doi.org/10.1007/978-3-319-91341-4_2

[14] Lampinen J., Storn R. Differential evolution. New optimization techniques in engineering. Berlin, Springer Heidelberg, 2004, pp. 123--166. DOI: https://doi.org/10.1007/978-3-540-39930-8_6

[15] Dorigo M., Stutzle T. Ant colony optimization. Overview and recent advances. Handbook of metaheuristics. Cham, Springer Nature, 2010, pp. 227--263. DOI: https://doi.org/10.1007/978-1-4419-1665-5_8

[16] Shah-Hosseini H. Problem solving by intelligent water drops. Proc. IEEE Congress on Evolutionary Computation, 2007, pp. 3226--3231. DOI: https://doi.org/10.1109/CEC.2007.4424885

[17] Lin S., Kernigan B.W. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 1973, vol. 21, no. 2, pp. 498--516.

[18] Semenkin E., Semenkina M. Self-configuring genetic algorithm with modified uniform crossover operator. ICSI 2012. Berlin, Springer Heidelberg, 2012, pp. 414--421. DOI: https://doi.org/10.1007/978-3-642-30976-2_50

[19] Meyer-Nieberg S., Beyer H.-G. Self-adaptation in evolutionary algorithms. Parameter setting in evolutionary algorithm. Cham, Springer Nature, 2007, pp. 47--75. DOI: https://doi.org/10.1007/978-3-540-69432-8_3

[20] Семенкин Е.С., Семенкина М.Е. Проектирование ансамблей интеллектуальных информационных технологий самоконфигурируемым алгоритмом генетического программирования. Вестник СибГАУ, 2012, № 4, с. 89--96.

[21] Аплеснин С.С., Жуков В.Г., Попов Е.А. и др. Исследование коэволюционного алгоритма генетического программирования и его применение в задаче моделирования фазовых границ магнитного состояния кристалла. Вестник СибГАУ, 2011, № 5, с. 9--14.

[22] Емельянова М.Н., Семенкин Е.С. Исследование эффективности коэволюционного алгоритма. Вестник СибГАУ, 2004, № 6, с. 28--34.

[23] Ахмедова Ш.А., Становов В.В., Семенкин Е.С. Кооперация бионического и эволюционного алгоритмов для задач проектирования искусственных нейронных сетей. Журнал СФУ. Математика и физика, 2018, т. 11, № 2, с. 148--158.

[24] Brester C., Ryzhikov I., Semenkin E., et al. On island model performance for cooperative real-valued multi-objective genetic algorithms. ICSI 2018. Cham, Springer Nature, 2018, pp. 210--219. DOI: https://doi.org/10.1007/978-3-319-93815-8_21

[25] Al-Betar M.A. Island-based harmony search algorithm for non-convex economic load dispatch problems. J. Electr. Eng. Technol., 2021, vol. 16, no. 4, pp. 1985--2015. DOI: https://doi.org/10.1007/s42835-021-00758-w

[26] Awadallah M.A., Al-Betar M.A., Bolaji A.L., et al. Island artificial bee colony for global optimization. Soft Comput., 2020, vol. 24, no. 17, pp. 13461--13487. DOI: https://doi.org/10.1007/s00500-020-04760-8

[27] Duarte G.R., de Lima B.S.L.P. Differential evolution variants combined in a hybrid dynamic island model. IEEE CEC, 2020. DOI: https://doi.org/10.1109/CEC48606.2020.9185579

[28] Abed-Alguni B.H., Paul D. Island-based Cuckoo Search with elite opposition-based learning and multiple mutation methods for solving optimization problems. Soft Comput., 2022, vol. 26, no. 7, pp. 3293--3312. DOI: https://doi.org/10.1007/s00500-021-06665-6

[29] Alvarez-Mamani E., Enciso-Rodas L., Ayala-Rincon M., et al. Parallel social spider optimization algorithms with island model for the clustering problem. SIMBig 2020. Cham, Springer Nature, 2020, pp. 122--138. DOI: https://doi.org/10.1007/978-3-030-76228-5_9

[30] Li J., Gonsalves T. Parallel hybrid island metaheuristic algorithm. IEEE Access, 2022, vol. 10, pp. 42268--42286. DOI: https://doi.org/10.1109/ACCESS.2022.3165830

[31] Da Silveira L.A., Soncco-Alvarez J.L., de Lima T.A., et al. Behavior of bioinspired algorithms in parallel island models. IEEE CEC, 2020. DOI: https://doi.org/10.1109/CEC48606.2020.9185732