The R-PSO algorithm solving multi-skill resource-constrained project scheduling problem
214 viewsDOI:
https://doi.org/10.54939/1859-1043.j.mst.CSCE5.2021.71-82Keywords:
Swarm Intelligence; Evolutionary Computing; Optimization Methods; Resource-Constrained Project Scheduling.Abstract
The Multi-Skill Resource-Constrained Project Scheduling Problem (MS-RCPSP) is a combinational optimization problem with many applications in science and practical areas. This problem aims to find out the feasible schedule for the completion of projects and workflows that is minimal duration or cost (or both of them - multi objectives). The researches show that MS-RCPSP is classified into NP-Hard classification, which could not get the optimal solution in polynomial time. Therefore, we usually use approximate methods to carry out the feasible schedule. There are many publication results for that problem based on evolutionary methods such as GA, Greedy, Ant, etc. However, the evolutionary algorithms usually have a limitation that is fallen into local extremes after a number of generations. This paper will study a new method to solve the MS-RCPSP problem based on the Particle Swarm Optimization (PSO) algorithm that is called R-PSO. The new improvement of R-PSO is re-assigning the resource to execute solution tasks. To evaluate the new algorithm's effectiveness, the paper conducts experiments on iMOPSE datasets. Experimental results on simulated data show that the proposed algorithm finds a better schedule than related works.
References
[1]. A.H. Hosseinian, V. Baradaran, "An Evolutionary Algorithm Based on a Hybrid Multi-Attribute Decision Making Method for the Multi-Mode Multi-Skilled Resource-Constrained Project Scheduling Problem.", Journal of Optimization in Industrial Engineering, 12.2, pp. 155-178,2019.
[2]. A.H. Hosseinian, V. Baradaran, "Detecting communities of workforces for the multi-skill resource-constrained project scheduling problem: A dandelion solution approach.", Journal of Industrial and Systems Engineering, pp. 72-99, 12.2019.
[3]. A.H. Hosseinian, V. Baradaran, "P-GWO and MOFA: two new algorithms for the MSRCPSP with the deterioration effect and financial constraints (case study of a gas treating company).", Applied Intelligence, 50 , pp. 2151-2176 , 2020.
[4]. F. Black, and M. Scholes, “The pricing of options and corporate liabilities”, Journal of Political Economy, 81, pp. 637-654, 1973
[5]. H. Li, K. Womer, “Stochastic Resource-Constrained Project Scheduling and Its Military Applications”, IEEE Trans Computer, 65(12), pp. 3702–3712, 2016.
[6]. H. Najafzad, H. Davari-Ardakani, R. Nemati-Lafmejani, "Multi-skill project scheduling problem under time-of-use electricity tariffs and shift differential payments.", Energy Journal, vol. 168, pp. 619-636, Elsevier,2019.
[7]. J. Kennedy, R. Eberhart, "Particle Swarm Optimization", IEEE International Conference on Neural Networks, 1995.
[8]. M. Skowroński, P.B. Myszkowski, P. Kwiatek, M. Adamski, "Tabu Search approach for Multi–Skill Resource–Constrained Project Scheduling Problem", Annals of Computer Science and Information Systems, Volume 1, Proceedings of the 2013 Federated Conference on Computer Science and Information Systems, pp. 153-158, 2013.
[9]. O. Sinnen, “Task scheduling for parallel systems”, Published by JohnWiley & Sons, Inc., Hoboken, New Jersey, Vol 60, 2007.
[10]. P.B. Myszkowski, M. Laszczyk, I. Nikulin, M. Skowro, “iMOPSE: a library for bicriteria optimization in Multi-Skill Resource-Constrained Project Scheduling Problem”, Soft Computing Journal, 23: 32397, 2019.
[11]. P.B. Myszkowski, M. Skowroński, "Specialized genetic operators for Multi–Skill Resource–Constrained Project Scheduling Problem", 19th International Conference on Soft Computing – Mendel 2013, pp. 57-62, 2013.
[12]. P.B. Myszkowski, M. Skowroński, L. Olech, K. Oślizło, "Hybrid Ant Colony Optimization in solving Multi–Skill Resource–Constrained Project Scheduling Problem", Soft Computing Journal, Volume 19, Issue 12, pp.3599–3619, 2015.
[13]. P.B. Myszkowski, M.E. Skowronski, K.Sikora, “A new benchmark dataset for Multi-Skill Resource-Constrained Project Scheduling Problem”, Computer Science and Information Systems, ACSIS, Vol. 5, pp. 129–138, 2015. DOI: 10.15439/2015F273.
[14]. R. Klein: “Scheduling of Resource-Constrained Projects”, Springer Science & Business Media, Vol. 10, 2012.
[15]. R. Kolisch, A. Sprecher, “PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program.”, European journal of operational research, 96(1), pp.205-216, 1997.
[16]. S. Javanmard, B. Afshar-Nadjafi, S.T. Niaki, "Preemptive multi-skilled resource investment project scheduling problem: Mathematical modeling and solution approaches.", Computers & Chemical Engineering, 96, pp. 55-68, 2017.
[17]. W. Guo, J.H. Park, L.T. Yang, A.V. Vasilakos, N. Xiong, G. Chen, "Design and Analysis of a MST-Based Topology Control Scheme with PSO for Wireless Sensor Networks,", 2011 IEEE Asia-Pacific Services Computing Conference, Jeju Island, pp. 360-367, 2011. doi: 10.1109/APSCC.2011
[18]. Huu Dang Quoc, Loc Nguyen The, Cuong Nguyen Doan, Toan Phan Thanh, Naixue Xiong, “Intelligent Differential Evolution Scheme for Network Resources in IoT”, Scientific Programming (IF:1.28, Q3), Volume 2020, Article ID 8860384 | 12, 2020. DOI: 10.1155/2020/8860384
[19]. H.N.S. Krishnamoorthy, Z. Jacob, E. Narimanov, I. Kretzschmar, V.M. Menon, Science 336 (2012) 205.
