MODIFIED GENETIC PROJECT PLANNING ALGORITHM IMPLEMENTED WITH THE USE OF CLOUD COMPUTING
Abstract
The paper proposes a structure of a modified genetic algorithm for solving resource constrained project scheduling problem implemented with the use of cloud computing, a computational experiment was conducted, during which the results of the proposed algorithm were compared with the best known, at the moment, results. Based on the results of the experiment, it was concluded that the proposed algorithm can be used to plan the work of real projects, since it is possible to draw up schedules for projects with the number of works n = 90 for an acceptable period of time. When planning projects with the number of jobs n = 30, n = 60, n = 90, 120, the execution time of the proposed algorithm was less than the execution time of the standard genetic algorithm by 2.8, 4, 5.5 and 6.8 times, respectively. Due to the fact that the task of constructing a project schedule taking into account limited resources is NP-difficult, the problem of creating new and modifying existing methods for solving it remains relevant. For planning projects with a large number of works, it is advisable to use cloud computing, since planning such projects can require a lot of time and computing resources. In this regard, the algorithm proposed in this paper differs from the existing ones by using cloud computing to distribute the load between workstations on which this algorithm is simultaneously running. The use of modified operators in the genetic algorithm, as well as the use of cloud infrastructure as a service for implementing a distributed genetic algorithm, determines the scientific novelty of the study.
References
Approaches and Solutions/ M. Abdolshah, International Transaction Journal of Engineering,
Management, & Applied Sciences & Technologies, 2014, No. 1, pp. 253-286.
2. Shirzadeh Chaleshtarti A., Shadrokh S., & Fathi Y. Branch and bound algorithms for resource
constrained project scheduling problem subject to nonrenewable resources with prescheduled
procurement, Mathematical Problems in Engineering, 2014.
3. Azizoglu M., Çetinkaya F.C., & Pamir S.K. LP relaxation-based solution algorithms for the
multi-mode project scheduling with a non-renewable resource, European Journal of Industrial
Engineering, 2015, No. 9 (4), pp. 450-469.
4. Daniel Morillo-Torres, Luis Fernando Moreno-Velásquez & Francisco Javier Díaz-Serna.
A branch and bound hybrid algorithm with four deterministic heuristics for the resource constrained
project scheduling problem (RCPSP). – 2014.
5. Zhenyuan L., & Hongwei W. Heuristic algorithm for RCPSP with the objective of minimizing
activities' cost, Journal of Systems Engineering and Electronics, 2006, Vol. 17 (1), pp. 96-102.
6. Zhu X., Ruiz R., Li S., & Li X. An effective heuristic for project scheduling with resource availability
cost, European Journal of Operational Research, 2017, Vol. 257 (3), pp. 746-762.
7. Gutierrez-Franco E. A Genetic Algorithm for the Resource Constrained Project Scheduling
Problem (RCPSP), International Transaction Journal of Engineering, Management, & Applied
Sciences & Technologies, 2014, No. 1, pp. 13-22.
8. Yuan X., Liu J., & Wimmers M.O. A multi-agent genetic algorithm with variable neighborhood
search for resource investment project scheduling problems, In 2015 IEEE Congress on Evolutionary
Computation (CEC), 2015, May, pp. 23-30. IEEE.
9. Vanucci S.C., Carrano E.G., Bicalho R., & Takahashi R.H. A modified NSGA-II for the
Multiobjective Multi-mode Resource-Constrained Project Scheduling Problem, In 2012 IEEE
Congress on Evolutionary Computation, 2012, June, pp. 1-7. IEEE.
10. Vartouni A.M., & Khanli L.M. A hybrid genetic algorithm and fuzzy set applied to multimode
resource-constrained project scheduling problem, Journal of Intelligent & Fuzzy Systems,
2014, Vol. 26 (3), pp. 1103-1112.
11. Xiao J., Wu Z., Hong X.X., Tang J.C., & Tang Y. Integration of electromagnetism with multiobjective
evolutionary algorithms for RCPSP, European Journal of Operational Research,
2016, Vol. 251 (1), pp. 22-35.
12. Sebt M.H., Afshar M.R., & Alipouri Y. Hybridization of genetic algorithm and fully informed
particle swarm for solving the multi-mode resource-constrained project scheduling problem,
Engineering Optimization, 2017, Vol. 49 (3), pp. 513-530.
13. Gomes H.C., das Neves F.D.A., & Souza M.J.F. Multi-objective metaheuristic algorithms for
the resource-constrained project scheduling problem with precedence relations, Computers &
Operations Research, 2014, Vol. 44, pp. 92-104.
14. Kadam S.U., & Kadam N.S. Solving resource-constrained project scheduling problem by genetic
algorithm, In Business and Information Management (ICBIM), 2014 2nd International
Conference on, 2014, January, pp. 159-164. IEEE.
15. Lazarev A.A., Gafarov E.R. Teoriya raspisaniy. Zadachi i algoritmy: ucheb. posobie [he scheduling
theory. Problems and algorithms: textbook]. Moscow: Moskovskiy gosudarstvennyy
universitet im. M.V. Lomonosova, 2011, 222 p.
16. Vil'chinskiy N. Ot khraneniya dannykh k upravleniyu informatsiey [From data storage to information
management]. Piter, 2016, 544 p.
17. Gladkov L.A., Zinchenko L.A., Kureychik V.V. i dr. Metody geneticheskogo poiska [Genetic
search methods]. Taganrog: Izd-vo TRTU, 2002.
18. Kureychik V.V., Sorokoletov P.V. Kontseptual'naya model' predstavleniya resheniy v geneticheskikh
algoritmakh [A conceptual model for representing solutions in genetic algorithms], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2008, No. 9 (86), pp. 7-12.
19. Shevlyakov A.O., Matveev M.G. Reshenie RCPSP pri nechetkikh trudozatratakh vypolneniya
operatsiy [Rcpsp solution for fuzzy labor costs of performing operations], Vestnik VGU
[Vestnik VSU], 2015, No. 4, pp. 119-123.
20. Gonçalves José & Resende Mauricio. A multi-population genetic algorithm for a constrained
two-dimensional orthogonal packing problem, J. Comb. Optim., 2011, Vol. 22, pp. 180-201.
Doi 10.1007/s10878-009-9282-1.
21. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy: ucheb, posobie [Genetic
algorithms: a textbook]. 2nd ed. Moscow: Fizmatlit. 2006, 320 p.
22. Kureichik V.V., Kureichik V.M. Genetic search-based control, Automation and Remote Control,
2001, Vol. 62, No. 10, pp. 1698-1710.
23. Samad J., Loke S.W. and Reed K. Quantitative Risk Analysis for Mobile Cloud Computing:
A Preliminary Approach and a Health Application Case Study, 12th IEEE International Conference
on Trust, Security and Privacy in Computing and Communications, Melbourne, VIC,
2013, pp. 1378-1385. Doi: 10.1109/TrustCom.2013.166.
24. Habibi, Farhad & Barzinpour, Farnaz & Sadjadi, Seyed. Resource-constrained project scheduling
problem: review of past and recent developments, Journal of Project Management, 2018,
No. 3, pp. 55-88. 10.5267/j.jpm.2018.1.005.
25. Mogilev A.A. Obzor metodov resheniya zadach teorii raspisaniy [Review of methods for solving
problems in the theory of schedules], Informatika, vychislitel'naya tekhnika i inzhenernoe
obrazovanie [Informatics, computer engineering and engineering education], 2019, Vol. 37, No. 2.