Solving a multicriteria scheduling problem using a genetic algorithm

Main Article Content

Alina Kazmirchuk
Olena Zhdanova
Volodymyr Popenko
Maiia Sperkach

Abstract

The work is devoted to the multiobjective task of scheduling, in which a given set of works must be performed by several performers of different productivity. A certain number of bonuses is accrued for the work performed by the respective executor, which depends on the time of work performance. The criteria for evaluating the schedule are the total time of all jobs and the amount of bonuses spent. In the research the main approaches to solving multiobjective optimization problems were analyzed, based on which the Pareto approach was chosen. The genetic algorithm was chosen as the algorithm. The purpose of this work is to increase the efficiency of solving multicriteria optimization problems by implementing a heuristic algorithm and increase its speed. The tasks of the work are to determine the advantages and disadvantages of the approaches used to solve multicriteria optimization problems, to develop a genetic algorithm for solving the multicriteria scheduling problem and to study its efficiency. Operators of the genetic algorithm have been developed, which take into account the peculiarities of the researched problem and allow to obtain Pareto solutions in the process of work. Due to the introduction of parallel calculations in the implementation of the genetic algorithm, it was possible to increase its speed compared to the conventional version. The developed algorithm can be used in solving the problem of optimal allocation of resources, which is part of the system of accrual of bonuses to employees.

Article Details

Section
Intelligent information systems
Author Biographies

Alina Kazmirchuk, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

master student of Computer-aided Management and Data Processing Systems Department

Olena Zhdanova, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

PhD in Technical science, Associate Professor of Computer-aided Management and Data Processing Systems Department

Volodymyr Popenko, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

PhD in Technical science, Associate Professor of Computer-aided Management and Data Processing Systems Department

Maiia Sperkach, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv

PhD in Technical science, Associate Professor of Computer-aided Management and Data Processing Systems Department

References

Coello, C.A.C. (2018), “Multi-objective Optimization”, Martí R., Panos P., Resende M. (eds), Handbook of Heuristics, Spring-er, Chamm, DOI: https://doi.org/10.1007/978-3-319-07153-4_17-1.

Chiandussi, G., Codegone, M. Ferreroc, S. & Varesio, F.E. (2012), “Comparison of multi-objective optimization methodologies for engineering applications”, Computers & Mathematics with Applications, Vol. 63, Is. 5, pp. 912-942, DOI: https://doi.org/10.1016/j.camwa.2011.11.057.

Polkovnykova, N.A., Kurejchyk, V.M. (2015), “Multiobjective optimization based on evolutionary algorithms”, Izvestiya SFedU. Engineering Sciences, No. 2(163), pp. 149-162.

Marchenko, I.V. (2020), “Topic 8. Multiobjective optimization”, Economic and mathematical methods: lecture notes, IBI, Mos-cow, available at: http://eos.ibi.spb.ru/umk/4_4/5/print/5_R1_T8.pdf.

Ashis, K.M., Mohapatra, Yo., Anil, K.M. (2012), “Multi-Objective Genetic Algorithm: A Comprhensive Survey”, Internation-al Journal of Emerging Technology and Advanced Engineering, Vol. 3, Is. 2, pp. 81-90.

Chang, K. (2015), “Multiobjective Optimization and Advanced Topics”, e-Design: Computer-Aided Engineering Design, Academic Press, pp. 1105-1173, DOI: https://doi.org/10.1016/B978-0-12-382038-9.00019-3.

Tamil Selvi, S., Baskar S. & Rajasekar S. (2018), “Application of Evolutionary Algorithm for Multiobjective Transformer Design Optimization”, Classical and Recent Aspects of Power System Optimization, pp. 463-504, DOI: https://doi.org/10.1016/B978-0-12-812441-3.00017-3.

Ouattara, A., Pibouleau, L.,Azzaro-Pantel, C., & Domenech, S. (2013), “Eco-design and Life Cycle Assessment of a chemical process: the case study of HDA (Pareto Front)”, Computer Aided Chemical Engineering, Vol. 32, pp. 727-732, DOI: https://doi.org/10.1016/B978-0-444-63234-0.50122-6.