Nature-Inspired Algorithms for Solving a Hierarchical Scheduling Problem in Short-Term Production Planning

The paper deals with the scheduling problem relevant in many fields, such as project management, lesson scheduling or production scheduling. In practice, using optimisation methods to solve the scheduling problem is considerably restricted by the fact that in the real world, problem statement involves high dimensionality, high production process complexity and many nontrivial constraints. These specifics mean that even merely searching for a feasible solution becomes a difficult task. Consequently, in order to solve the problem in a reasonable amount of time it is necessary to use problem-oriented heuristics. Ensuring manufacturing process stability involves respecting all constraints, but at the same time, short-term production planning demands fast solutions whenever there is a change of state. We propose to implement a hierarchical problem structure that puts the travelling salesman problem at the top and replaces the nested resource-constrained project scheduling problem with a simulation model. The paper considers using such algorithms as the Lin --- Kernighan heuristic, the genetic algorithm and the ant colony optimization. We study the efficiency of employing the algorithms mentioned above to solve the scheduling problem in the statement proposed

References

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

[2] Forndron F., Liebermann T., Thurner M., et al. mySAP ERP roadmap: business processes, capabilities, and complete upgrade strategy. SAP PRESS, 2006.

[3] Pazhinskaya A.A. ERP-systems, their purpose and features. Microsoft Dynamics Software overview. Molodezhnyy nauchno-tekhnicheskiy vestnik, 2015, no. 3 (in Russ.). Available at: http://ainsnt.ru/doc/770644.html

[4] Gracheva E.V., Pchelintseva O.N. Planning and production management of the enterprises on the basis of system Оracle Е-Business Suite. Izvestiya PGPU im. V.G. Belinskogo, 2011, no. 26, pp. 547–549 (in Russ.).

[5] Adueva T.V., Akhaev A.V., Khodashinskiy I.A. Production rule system for the choice of software products of system “1C:Enterprise 8”. Biznes-informatika [Business Informatics], 2012, no. 1 (19), pp. 55–61 (in Russ.).

[6] Frolov E.B., Zagidullin R.R. ES-systems as they are or evolution of production planning systems. Stanochnyy park, 2008, no. 10 (55), pp. 31–37 (in Russ.).

[7] Gorodetskaya O.Yu., Gobareva Ya.L. CRM system as a strategy for company’s business management. Transportnoe delo Rossii, 2014, no. 4, pp. 169–172 (in Russ.).

[8] Dzhukha V.M., Kirillov D.O. Potential advantages of APS systems in sales and operational planning. Upravlenie ekonomicheskimi sistemami, 2013, no. 7 (55), pp. 19 (in Russ.).

[9] Idzikovskiy V.I., Gorshkova E.A. Is LIMS an automated control system for laboratories or something more? Sovremennaya laboratornaya praktika, 2012, no. 3 (19), pp. 10–24 (in Russ.).

[10] Ambartsumyan A.A., Khadeev A.S. Functionality analysis of equipment maintenance management systems. Problemy upravleniya [Control Sciences], 2005, no. 6, pp. 2–12 (in Russ.).

[11] Morgunova O.V. [Formation of a unified information space of the enterprise]. Sb. tr. X Vseros. nauch.-prakt. konf. “Matematicheskie modeli sovremennykh ekonomicheskikh protsessov, metody analiza i sinteza ekonomicheskikh mekhanizmov. Aktual’nye problemy i perspektivy menedzhmenta organizatsiy v Rossii” [Proc. X Russ. sci.-pract. conf. “Mathematical models of modern economic processes, methods of economic mechanisms analysis and synthesis. Topical problems and prospects of organization management in Russia”]. Samara, SSC RAS Publ., 2015, pp. 130–139 (in Russ.).

[12] Simonova S.I. Data mining for CRM tasks. INJOIT, 2015, no. 2, pp. 17–22 (in Russ.).

[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] Anichkin A.S., Semenov V.A. A survey of emerging models and methods of scheduling. Trudy ISP RAN [Proceedings of ISP RAS], 2014, vol. 26, no. 3, pp. 5–50 (in Russ.).

[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] Gromov S.A., Tarasov V.B. Integrated intelligent systems of production planning and scheduling. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, no. 7, pp. 60–67 (in Russ.).

[20] Skobtsov Yu.A., Chengar’ O.V., Skakovskaya A.N. Multi-criteria ant algorithm for production schedule optimization. Matematicheskie metody v tekhnike i tekhnologiyakh, 2016, no. 12 (94), pp. 245–253 (in Russ.).

[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 M., 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] Semenkina O.E., Semenkina O.E. Effectiveness investigation of biology-inspired algorithms for combinatorial optimization. Programmnye produkty i sistemy [Software & Systems], 2013, no. 3, p. 23 (in Russ.).

[26] Semenkina O.E. Effectiveness comparison of ant colony and genetic algorithms for solving combinatorial optimization problem. Vestnik SibGAU, 2012, no. 4 (44), pp. 96–98 (in Russ.).

[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. Zhurnal Sibirskogo federal’nogo universiteta. Seriya: Matematika i fizika [Journal of Siberian Federal University. Mathematics & Physics], 2017, vol. 10, no. 4, pp. 463–473.

[29] Semenkina O.E., Popov E.A., Semenkina O.E. Self-configuring evolutionary algorithms for travelling salesman problem. Vestnik SibGAU, 2013, no. 4 (50), pp. 134–139 (in Russ.).