МОДИФИЦИРОВАННЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПЛАНИРОВАНИЯ ПРОЕКТОВ, РЕАЛИЗОВАННЫЙ С ИСПОЛЬЗОВАНИЕМ ОБЛАЧНЫХ ВЫЧИСЛЕНИЙ
Аннотация
Предложена структура модифицированного генетического алгоритма для решения
задачи построения расписания проекта с учетом ограниченности ресурсов, реализова н-
ного с использованием облачных вычислений, проведен вычислительный эксперимент, в
ходе которого было произведено сравнение результатов работы предложенного алг о-
ритма с лучшими из известных, на данный момент, результатами. Исходя из результа-
тов эксперимента был сделан вывод, о том, что предложенный алгоритм может быт ь
использован для планирования работ реальных проектов, так как с его помощью во з-
можно составлять расписания для проектов с количеством работ n = 90 за приемлемый
промежуток времени. При планировании проектов с количеством работ n = 30, n = 60,
n = 90, 120 время выполнения предложенного алгоритма было меньше, чем время выпо л-
нения стандартного генетического алгоритма в 2.8, в 4, в 5.5 и 6.8 раз соответственно.
В связи с тем, что задача построения расписания проекта с учетом ограниченности
ресурсов является NP-трудной, проблема создания новых и модификации существующих
методов её решения по-прежнему остается актуальной. Для планирования проектов с
большим количеством работ целесообразно использовать облачные вычисления, так как
планирование таких проектов может потребовать много времени и вычислительных
ресурсов. Использование облачных вычислений позволит сократить время выполнения
генетического алгоритма за счет предоставления поставщиком облачного сервиса
больших вычислительных ресурсов. В связи с этим, предложенный в данной работе алго-
ритм отличается от уже имеющихся использованием облачных вычислений для распр е-
деления нагрузки между рабочими станциями, на которых одновременно выполняется
данный алгоритм. Применение в генетическом алгоритме модифицированны х операто-
ров, а также использование облачной инфраструктуры как услуги для реализации ген е-
тического алгоритма при решении задачи планирования проектов определяет научную
новизну исследования.
Литература
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.
