GENETIC ALGORITHM APPLICATION FOR MULTI-CRITERIA SCHEDULING PROBLEM

Arkhipov Ivan V.

doi:10.17586/2226-1494-2015-15-3-525-531

2015 , VOLUME 15, NUMBER 3 ( May-June )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

doi: 10.17586/2226-1494-2015-15-3-525-531

GENETIC ALGORITHM APPLICATION FOR MULTI-CRITERIA SCHEDULING PROBLEM

I. V. Arkhipov

Read the full article

Article in English

For citation: Arkhipov I.V. Genetic algorithm application for multi-criteria scheduling problem. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2015, vol.15, no. 3, pp. 525–531.

Abstract

The paper describes mathematical model and method of task solution for defining an enterprise work performance schedule. Two-stage feedstock processing is supposed to exist at the enterprise. At the first stage the sawing process into semimanufactured products is done. The second stage (finished products manufacturing stage) includes durable processing of obtained semimanufactured products at one of the interchangeable work centers. The sawing process into semimanufactured products is carried out according to a plan, developed in advance and in compliance with technological charts. Scheduling consists of separate cutting calculation and planning of all feedstock cutting with the aim of the most effective specification task performance based on available reserves. Following the cutting plan, an enterprise work performance schedule is created. This schedule consists of the cutting sequence with volume, start and end time, and plan for loading of after-treatment. The solution to this problem becomes more involved due to the necessity of taking into account all features, limitations and parameters of process equipment, as well as of raw material and production orders. Special method based on genetic algorithm has been proposed for handling the problem. The algorithm has been tested on several different realproduction plans. Its efficiency estimation is given. The software systemimplemented on the proposed algorithm has been tested on real operating data of several sawmills. Reduction of machine idle time and incomplete production decrease has been confirmed by the enterprise specialists.

Keywords: genetic algorithms, dynamic programming, theory of scheduling.

References

1. Kostenko V.A. Scheduling algorithms for real-time computing systems admitting simulation models. Programming and Computer Software, 2013, vol. 39, no. 5, pp. 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, vol. 29, no. 4, pp. 199–209. doi: 10.1023/A:1024918625291

3. Goncharov E.N. Stokhasticheskii zhadnyi algoritm dlya zadachi kalendarnogo planirovaniya s ogranichennymi resursami [A stochastic greedy algorithm for the resource-constrained project scheduling problem]. Diskretnyi Analiz i Issledovanie Operatsii, 2014, vol. 21, no. 3, pp. 11–24.

4. Eremeev A.V., Kovalenko Yu.V. O slozhnosti optimal'noi rekombinatsii dlya odnoi zadachi sostavleniya raspisanii s perenaladkami [On the complexity of the optimal combination for the problem of scheduling with changeovers]. Diskretnyi Analiz i Issledovanie Operatsii, 2012, vol. 19, no. 3, pp. 13–26.

5. Velikanova Yu.Yu. Otsenki vremeni raboty algoritmov lokal'nogo spuska dlya zadachi postroeniya raspisanii na parallel'nykh mashinakh [Running time of local search algorithms for a scheduling problem on the parallel machines]. Diskretnyi Analiz i Issledovanie Operatsii, 2012, vol. 19, no. 5, pp. 21–34.

6. Voronin A.V., Kuznetsov V.A., Shabaev A.I., Arhipov I.V., Kashevnik A.M. Razrabotka i realizatsiya sistemy planirovaniya lesopil'nym proizvodstvom [Research and development of a software system for sawmill operation planning]. SPIIRAS Proceedings, 2012, no. 4 (23), pp. 400–415.

7. Voronin A.V., Kuznetsov V.A., Arkhipov I.V., Shabaev A.I. Software system for sawmill operation planning. Proc. 12th Conference of FRUCT Association. St. Petersburg, Russia, 2012, pp. 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. 14th Conference of Open Innovation Association, FRUCT. Espoo, Finland, 2013, pp. 140–147. doi: 10.1109/FRUCT.2013.6737956

9. Arkhipov I.V. Matematicheskie modeli raskroya lesosyr'ya v zadachakh planirovaniya i upravleniya lesopil'nym proizvodstvom [Mathematical models and geometrical features of wood sawing in planning and management of sawmill industry]. Uchenye Zapiski PetrGU. Seriya Estestvennye i Tekhnicheskie Nauki, 2013, no. 8 (137), pp. 93–97.

10. Arkhipov I.V. Matematicheskie modeli i opyt realizatsii sistemy planirovaniya raskroya lesosyr'ya [Mathematical model and experience of implementation of wood sawing planning software system]. Vestnik SPbSU. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya, 2014, no. 3, pp. 82–92.

11. Nogin V.D. Prinyatie Reshenii v Mnogokriterial'noi Srede: Kolichestvennyi Podkhod [Decision-Making in Multicriteria Environment: a Quantitative Approach]. Moscow, Fizmatlit Publ., 2002, 176 p.

12. Urban A.R., Kuznetsov V.A. Matematicheskie modeli i metody ucheta srokov produktsii v zadache raskroya tamburov bumagodelatel'nykh mashin [Mathematical models and methods of output production timeline consideration in cutting reels of paper machine]. Uchenye Zapiski PetrGU. Seriya Estestvennye i Tekhnicheskie Nauki, 2014, no. 4 (141), pp. 112–115.

13. Urban A.R. Reshenie zadachi poiska optimal'nogo stolbtsa v usloviyakh optimal'nogo raskroya bumazhnogo polotna [Solution of the problem of finding the optimal column in terms of optimal paper cutting]. Vestnik SPbSU. Seriya 10. Prikladnaya Matematika. Informatika. Protsessy Upravleniya, 2015, no. 1, pp. 100–106.

14. Afanasyeva A.S., Buzdalov M.V. Vybor funktsii prisposoblennosti osobei geneticheskogo algoritma s pomoshch'yu obucheniya s podkrepleniem [Fitness function choosing for genetic algorithms with reinforcement learning]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2012, no. 1 (77), pp. 77–81.

15. Stepanov D.V., Shalyto A.A. Ispol'zovanie geneticheskogo algoritma dlya poiska optimal'noi traektorii nablyudatelya [Genetic algorithm approach to observer's optimal trajectory design]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2012, no. 1 (77), pp. 90–95.

16. Asanov M.O., Baranskii V.A., Rasin V.V. Diskretnaya Matematika: Grafy, Matroidy, Algoritmy [Discrete Mathematics: Graphs, Matroids, Algorithms]. Izhevsk, Regulyarnaya i Khaoticheskaya Dinamika Publ., 2001, 288 p.

17. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. 2nd ed. Cambridge, MIT Press, 2006, 1312 p.

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

19. Kalenkova A.A. An algorithm of automatic workflow optimization. Programming and Computer Software, 2012, vol. 38, no. 1, pp. 43–56. doi: 10.1134/S0361768812010045

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