Cooperative Coevolution Hierarchical Self-Configuring Algorithm for Solving the Scheduling Problem

Abstract

To solve the problem of scheduling during operational production planning, the paper proposes to introduce a cooperative coevolution hierarchical self-configuring method based on the combinatorial and material bionic optimization algorithms. Combinatorial optimization was performed using the ant colony algorithm and the genetic algorithm, as well as their self-configuring versions. Similarly, classical and self-configuring well-known versions of the differential evolution algorithm and of the flocking and material genetic algorithms were used in material optimization. For comparison with the classical combinatorial algorithms, the smart drop algorithm and the Lin --- Kernighan heuristic were included. A corresponding hierarchical formulation of the scheduling problem was proposed, where at the top level, the combinatorial problem of finding the batch launching order was set, and the attached task consisted in finding the equipment priorities to increase the problem formulation flexibility while maintaining the approach universality. Three problem formulations were also considered. They included finding the batch launching order, selecting the operation priority order and finding material values of the operation priorities. In addition, production simulation model was introduced to include necessary nuances of the technological process. Effectiveness of using this methodology was demonstrated in comparison with other problem formulations and classical algorithms of combinatorial and material optimization. The proposed formulation of the problem provides significant possibilities for application in complex industries with technological processes requiring non-standard methods of description

The work was supported by the Ministry of Science and Higher Education of the Russian Federation (project no. FEFE-202300-0004)

Please cite this article in English as:

Semenkina O.E., Stanovov V.V., Popov E.A. Cooperative coevolution hierarchical self-сonfiguring algorithm for solving the scheduling problem. Herald of the Bauman Moscow State Technical University, Series Instrument Engineering, 2023, no. 4 (145), pp. 131--148 (in Russ.). DOI: https://doi.org/10.18698/0236-3933-2023-4-131-148

References

[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] Shevlyakov A.O., Matveev M.G. Solving RCPSP with uncertain duration times of activities. Vestnik VGU. Ser. Sistemnyy analiz i informatsionnye tekhnologii [Proceedings of Voronezh State University. Ser. Systems Analysis and Information Technologies], 2015, no. 4, pp. 121--125 (in Russ.).

[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] Semenkina O.E., Ryzhikov I.S., Lipinskiy L.V., et al. A method of production system modeling for operational planning. Sistemy upravleniya i informatsionnye tekhnologii, 2021, no. 3, pp. 17--24 (in Russ.).

[9] Semenkina O.E. Cooperative co-evolution of self-configuring bio-inspired algorithms for the scheduling problem. Sistemy upravleniya i informatsionnye tekhnologii, 2022, no. 1, pp. 63--68 (in Russ.).

[10] Anichkin A.S., Semenov V.A. A survey of emerging models and methods of scheduling. Trudy Instituta sistemnogo programmirovaniya RAN [Proceedings of ISP RAS], 2014, vol. 26, no. 3, pp. 5--50 (in Russ.). 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] Semenkin E.S., Semenkina M.E. Integration of intelligent information technologies ensembles with self-configuring genetic programming algorithm. Vestnik SibGAU [Vestnik SibSAU], 2012, no. 4, pp. 89--96 (in Russ.).

[21] Aplesnin S.S., Zhukov V.G., Popov E.A., et al. Research of coevolution genetic programming algorithm and its application in the problem of model analysis of phase boundaries of magnetic state of a crystal. Vestnik SibGAU [Vestnik SibSAU], 2011, no. 5, pp. 9--14 (in Russ.).

[22] Emelyanova M.N., Semenkin E.S. Effectiveness investigation of coevolutionary genetic algorithm for constrained optimization problems. Vestnik SibGAU [Vestnik SibSAU], 2004, no. 6, pp. 28--34 (in Russ.).

[23] Akhmedova Sh.A., Stanovov V.V., Semenkin E.S. Cooperation of bio-inspired and evolutionary algorithms for neural network design. Zhurnal SFU. Matematika i fizika [Journal of Siberian Federal University. Mathematics & Physics], 2018, vol. 11, no. 2, pp. 148--158 (in Russ.).

[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