Алгоритмы ускорения работы модификации метода муравьиных колоний для поиска рационального назначения сотрудников на задачи с нечетким временем выполнения

Аннотация

Подход, использующий нечеткое время для определения времени выполнения наукоемкого проекта, требует решения задачи назначения сотрудников по задачам. В этом случае для каждого сотрудника и каждой задачи, которую может выполнить сотрудник, назначается нечеткая функция выполнения задачи. Распределение сотрудников по задачам успешно решает модификация метода муравьиных колоний, работающая с графом решений. Но скорость и точность работы метода зависит от оптимальности установленных его параметров, и алгоритм подвержен «зацикливанию», ситуации, когда все агенты перемещаются по одному пути в графе решений, занося на него много весов и не имея возможности на следующих итерациях выбрать другой маршрут в графе решений. Решить данные проблемы предлагается путем сброса графа решения при различных методах определения момента «зацикливания». Момент зацикливания предлагается определять по статистическим параметрам, вычисленным на одной итерации алгоритма. Алгоритм определения зацикливания, при котором определяется, были ли найдены новые решения на итерации, показал более высокую производительность. Но данный подход требует хранения всех найденных решений, что хорошо работает в случае, если вычисление критерия занимает серьезное время моделирования. Кроме того идеи сброса графа решений позволяют решить некоторые проблемы установки неэффективных параметров метода муравьиных колоний. Для ускорения процесса нахождения рациональных путей в работе рассматривается возможность занесения различных начальных весов после сброса графа решений. Наиболее эффективным будет добавление весов от 2-х до 5-ти наилучших путей, найденных агентами за время работы метода муравьиных колоний. В дальнейшем предлагается рассматривать многокритериальную задачу о назначениях и различные алгоритмы применения нечетких множеств при календарном планировании задач.

Сведения об авторах

Vladimir Anatolyevich Sudakov, Финансовый университет при Правительстве Российской Федерации

профессор департамента анализа данных и машинного обучения, доктор технических наук, доцент

Alexander Mikhailovich Batkovsky, ЦНИИ "Электроника"

советник генерального директора, доктор экономических наук

Yuri Pavlovich Titov, Федеральный исследовательский центр "Информатика и управление" РАН

научный сотрудник Института проблем информатики Российской академии наук, кандидат технических наук

Литература

[1] de la Garza J.M., Kim K. Application of the Resource-Constrained Critical Path Method to Multiple Calendars and Progressed Schedules. In: Ariaratnam S.T., Rojas E.M. (ed.) Building a Sustainable Future. Proceedings of Construction Research Congress 2009. American Society of Civil Engineers; 2009. p. 916-925. (In Eng.) DOI: http://doi.org/10.1061/41020(339)93
[2] Kim K., de la Garza J.M. Critical Path Method with Multiple Calendars. Journal of Construction Engineering and Management. 2005; 13(3):330-342. (In Eng.) DOI: http://doi.org/10.1061/(ASCE)0733-9364(2005)131:3(330)
[3] Naili M., Naili M. Tari A. Uncertainty in the Pert’s Critical Path. International Journal of Science and Technology. 2018; 4(1):1-9. (In Eng.) DOI: http://doi.org/10.20319/mijst.2018.41.0109
[4] Bondarenko A.N., Shavrin A.V. PERT in project management. Upravlenie Proektami I Programmami = Project Management Journal. 2016; (1):68-78. Available at: https://www.elibrary.ru/item.asp?id=25441318 (accessed 02.09.2020). (In Russ., abstract in Eng.)
[5] Wilson J.M. Gantt Charts: A Centenary Appreciation. European Journal of Operational Research. 2003; 149(2):430-437. (In Eng.) DOI: http://doi.org/10.1016/S0377-2217(02)00769-5
[6] Chen S.P., Hsueh Y.J. A Simple Approach to Fuzzy Critical Path Analysis in Project Networks. Applied Mathematical Modelling. 2008; 32(7):1289-1297. (In Eng.) DOI: http://doi.org/10.1016/j.apm.2007.04.009
[7] Liu S.T. Fuzzy Activity Times in Critical Path and Project Crashing Problems. Cybernetics and Systems: An international Journal. 2003; 34(2):161-172. (In Eng.) DOI: http://doi.org/10.1080/01969720302865
[8] Popescu C.-C., Giuclea M. On Critical Path with Fuzzy Weights. Economic Computation and Economic Cybernetics Studies and Research. 2018; 52(4):49-60. (In Eng.) DOI: http://doi.org/10.24818/18423264/52.4.18.04
[9] Shih P.C. Analysis of critical paths in a project network with fuzzy activity times. European Journal of Operational Research. 2007; 183(1):442-459. (In Eng.) DOI: http://doi.org/10.1016/j.ejor.2006.06.053
[10] Zieliński P. On computing the latest starting times and floats of activities in a network with imprecise durations. Fuzzy Sets and Systems. 2005; 150(1):53-76. (In Eng.) DOI: http://doi.org/10.1016/j.fss.2004.08.007
[11] Nasution S.H. Fuzzy critical path method. IEEE Transactions on Systems, Man, and Cybernetics. 1994; 24(1):48-57. (In Eng.) DOI: http://doi.org/10.1109/21.259685
[12] Chen C.-T., Huang S.-F. Applying fuzzy method for measuring criticality in project network. Information Sciences. 2007; 177(12):2448-2458. (In Eng.) DOI: http://doi.org/10.1016/j.ins.2007.01.035
[13] Bushuyeva N., Bushuiev D., Bushuieva V. AGILE Leadership of Managing Innovation Projects. Innovate Technologies & Scientific Solutions for Industries. 2019; 4(10):77-84. (In Eng., abstract in Russ.) DOI: http://doi.org/10.30837/2522-9818.2019.10.077
[14] Koçyiğit Y., Akkaya B. The Role of Organizational Flexibility in Organizational Agility: A Research on SMEs. Business Management and Strategy. 2020; 11(1):110-123. (In Eng.) DOI: http://doi.org/10.5296/bms.v11i1.16867
[15] Sharifi H., Zhang Z. Agile manufacturing in practice-Application of a methodology. International Journal of Operations & Production Management. 2001; 21(5-6):772-794. (In Eng.) DOI: http://doi.org/10.1108/01443570110390462
[16] Sudakov V.A., Titov Yu.P. Solving the problem of determining the time of work by a group of employees using fuzzy sets. Open Education. 2019; 23(5):74-82. (In Russ., abstract in Eng.) DOI: http://doi.org/10.21686/1818-4243-2019-5-74-82
[17] Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies. In: Proceedings of the First European Conference on Artificial Life, ECAL’91. Elsevier, Paris, France; 1991. p. 134-142. (In Eng.)
[18] Dorigo M., Birattari M., Stutzle T. Ant colony optimization. IEEE Computational Intelligence Magazine. 2006; 1(4):28-39. (In Eng.) DOI: http://doi.org/10.1109/MCI.2006.329691
[19] Oliveira S., Hussin M.S., Roli A., Dorigo M., Stützle T. Analysis of the population-based ant colony optimization algorithm for the TSP and the QAP. In: 2017 IEEE Congress on Evolutionary Computation (CEC). San Sebastian; 2017. p. 1734-1741. (In Eng.) DOI: http://doi.org/10.1109/CEC.2017.7969511
[20] Pei Y., Wang W., Zhang S. Basic Ant Colony Optimization. In: 2012 International Conference on Computer Science and Electronics Engineering. Hangzhou; 2012. p. 665-667. (In Eng.) DOI: http://doi.org/10.1109/ICCSEE.2012.178
[21] Sudakov V.A., Titov Yu.P. Application of the Modified Method of Ant Colonies to Search for Rational Assignment of Employees to Tasks Using Fuzzy Sets. Statistics and Economics. 2020; 17(3):79-91. (In Russ., abstract in Eng.) DOI: http://doi.org/10.21686/2500-3925-2020-3-79-91
[22] Lootsma F.A. Stochastic and fuzzy PERT. European Journal of Operational Research. 1989; 43(2):174-183. (In Eng.) DOI: http://doi.org/10.1016/0377-2217(89)90211-7
[23] Sharafi M., Jolai F., Iranmanesh H., Hatefi S.M. A Model for Project Scheduling with Fuzzy Precedence Links. Australian Journal of Basic and Applied Sciences. 2008; 2(4):1356-1361. Available at: http://www.ajbasweb.com/old/ajbas/2008/1356-1361.pdf (accessed 02.09.2020). (In Eng.)
[24] Toljaga-Nikolić D.V., Petrović D.Č., Suknović M.M., Mihić M.M. Application of fuzzy PERT method in project planning. Technics. 2014; 69(4):679-686. (In Serbian, abstract in Eng.) DOI: http://doi.org/10.5937/tehnika1404679T
[25] Thaeir Ahmed Saadoon Al Samman, Ramadan M. Ramo Al Brahemi. Fuzzy PERT For Project Management. International Journal of Advances in Engineering & Technology. 2014; 7(4):1150-1160. Available at: https://www.ijaet.org/media/4I22-IJAET0722555_v7_iss4_1150-1160.pdf (accessed 02.09.2020). (In Eng.)
[26] Liberatore M.J. Critical Path Analysis With Fuzzy Activity Times. IEEE Transactions on Engineering Management. 2008; 55(2):329-337. (In Eng.) DOI: http://doi.org/10.1109/TEM.2008.919678
[27] Titov Yu.P. Modification of the Ant Colony Optimization for the Development of Software for Solving Multi-criterion Supply Management Problems. Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2017; 13(2):64-74. (In Russ., abstract in Eng.) DOI: http://doi.org/10.25559/SITITO.2017.2.222
Опубликована
2020-09-30
Как цитировать
SUDAKOV, Vladimir Anatolyevich; BATKOVSKY, Alexander Mikhailovich; TITOV, Yuri Pavlovich. Алгоритмы ускорения работы модификации метода муравьиных колоний для поиска рационального назначения сотрудников на задачи с нечетким временем выполнения. Международный научный журнал «Современные информационные технологии и ИТ-образование», [S.l.], v. 16, n. 2, p. 338-350, sep. 2020. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/640>. Дата доступа: 07 mar. 2021 doi: https://doi.org/10.25559/SITITO.16.202002.338-350.
Раздел
Прикладные проблемы оптимизации