AdaL-PSO A New Adaptive Algorithm for the Multi-Skilled Resource-Constrained Project Scheduling Problem: AdaL-PSO A New Adaptive Algorithm for the Multi-Skilled Resource-Constrained Project Scheduling Problem

Phan Thanh Toan; Do Van Tuan

doi:10.15625/2525-2518/17919

Author affiliations

Authors

Phan Thanh Toan ATC Group, Yen Phong Industrial Zone, Yen Trung Communes, Yen Phong District, Bac Ninh Province, Vietnam
Do Van Tuan ATC Group, Yen Phong Industrial Zone, Yen Trung Communes, Yen Phong District, Bac Ninh Province, Vietnam

DOI:

https://doi.org/10.15625/2525-2518/17919

Keywords:

Swarm Intelligence, Evolutionary Computing, Optimization Methods, Resource Constrained Project Scheduling, Particle Swarm Optimization

Abstract

MS-RCPSP is a combinatorial optimization problem that has many practical applications, this problem has been proven to belong to the NP-hard class, the approach to solving this problem is to use algorithms to find approximate solution. This paper proposed a New Adaptive Local Particle Swarm Optimization algorithm for the MS-RCPSP problem. The solution for the class of NP-Hard problems is to find approximate solutions using metaheuristic algorithms. However, most metaheuristic-based algorithms have a weakness that can be fallen into local extreme after a number of evolution generations. In this paper, we adopted a new adaptive nonlinear weight update strategy based on fitness value and new neighborhood topology for Particle Swarm Optimization algorithm, thereby helping to prevent PSO from falling into local extremes. The new algorithm is called AdaL-PSO. A numerical analysis is carried out using iMOPSE benchmark dataset and is compared with some other early algorithms. Results presented suggest the prospect of our proposed algorithm.

Downloads

Download data is not yet available.

References

AfsharN. B. - Multi-skilling in scheduling problems: A review on models, methods and applications, Computers & Industrial Engineering 151 (2021) 107004. https://doi.org/ 10.1016/j.cie.2020.107004.

Alirezaei, Mahsa, SeyedT. A. N., SeyedA. A. N. - A bi-objective hybrid optimization algorithm to reduce noise and data dimension in diabetes diagnosis using support vector machines, Expert Systems with Applications 127 (2019) 47-57.

Mejia, Oliver Polo, et al. - A new RCPSP variant to schedule research activities in a nuclear laboratory, 47th International Conference on Computers and Industrial Engineering (CIE47), 2017.

Blazewicz J., Lenstra J. K., Kan A. - Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics 5 (1983) 11-24.

Myszkowski, Paweł B., Marek E. S., Krzysztof S. - A new benchmark dataset for multi-skill resource-constrained project scheduling problem, Federated Conference on Computer Science and Information Systems (FedCSIS), IEEE, 2015. DOI: 10.15439/2015F273.

Yuanyuan Z., Naixue X., Kim T. - Channel assignment and scheduling in multichannel wireless sensor networks, 2008 33rd IEEE Conference on Local Computer Networks (LCN), Montreal, Que. (2008) 512-513.doi: 10.1109/LCN.2008.4664215.

Cheng H., Naixue X., Yang L. T. - Distributed Access Scheduling Algorithms in Wireless Mesh Networks, 22nd International Conference on Advanced Information Networking and Applications (aina 2008), Okinawa. (2008) 509-516.DOI: 10.1109/AINA.2008.29.

Wei G., Vasilakos A. V., Naixue X. - Scheduling Parallel Cloud Computing Services: An Evolutional Game, 2009 First International Conference on Information Science and Engineering, Nanjing. (2009) 376-379.DOI: 10.1109/ICISE.2009.1046.

Nie W., Naixue X., Park J. H., Yeo S. - A Fair-Oriented Two-Level Scheduling Scheme for Downlink Traffic in WiMAX Network, 2010 2nd International Conference on Information Technology Convergence and Services, Cebu. (2010) 1-6.DOI: 10.1109/ITCS.2010.5581291.

Zheng W.,Naixue X., Ghani N., Min P. A., Vasilakos A. V., Liang Z. - Adaptive scheduling for wireless video transmission in high-speed networks, 2011 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Shanghai. (2011) 180-185.DOI: 10.1109/INFCOMW.2011.5928803

Dong P., Xie J., Tang W., Xiong N., Zhong H., Vasilakos A. V. - Performance Evaluation of Multipath TCP Scheduling Algorithms, IEEE Access.7 (2019) 29818-29825.DOI: 10.1109/ACCESS.2019.2898110.

Klein R., Scheduling of Resource. - Constrained project, Springer Science Business Media NewYork, Kluwer Academic Publisher, ISBN 978-1-4613-7093-2, 2000.

Myszkowski P. B., Laszczyk M., Nikulin I., Skowronski E. - iMOPSE: a library for bicriteria optimization in Multi–Skill Resource–Constrained Project Scheduling Problem, Soft Computing. 23 (10) (2019) 3397-3410.

Cheng H., Xiong N., Huang X., Yang L. T. - An Efficient Scheduling Model for Broadcasting in Wireless Sensor Networks, 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, Cambridge, MA. (2013) 1417-1428.DOI: 10.1109/IPDPSW.2013.88

Lin B., Guo W., Xiong N., Chen G., Vasilakos A. V., Zhang H. - A Pretreatment Workflow Scheduling Approach for Big Data Applications in Multicloud Environments, IEEE Transactions on Network and Service Management 13 (3) (2016) 581-594.DOI: 10.1109/TNSM.2016.2554143.

Lin B., Guo W., Chen G., Xiong N., Li R. - Cost-Driven Scheduling for Deadline-Constrained Workflow on Multi-clouds, 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, Hyderabad 15 (4) (2015) 1191-1198. DOI: 10.1109/IPDPSW.2015.56.

Tan L., Zhu Z, Ge F., Xiong N. - Utility Maximization Resource Allocation in Wireless Networks: Methods and Algorithms, IEEE Transactions on Systems, Man, and Cybernetics: Systems. 45 (7) (2015) 1018-1034.DOI: 10.1109/TSMC.2015.2392719.

Guo P., Cheng W., Wang Y. - A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs, J. Ind. Manag. Optim. 10 (4) (2014) 1071-1090.

Kavitha S., Venkumar P. - A vibrant crossbreed social spider optimization with genetic algorithm tactic for flexible job shop scheduling problem, Measurement and Control 53 (1-2) (2020).

Agrawal, Prakash A., Choudhary A., Arvinder K. - An Effective Regression Test Case Selection Using Hybrid Whale Optimization Algorithm, International Journal of Distributed Systems and Technologies (IJDST) 11 (1) (2020) 53-67.

Guo W., Park J. H., Yang L. T., Vasilakos A. V., Xiong. N., Chen. G. - 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. (2011) 360-367.DOI: 10.1109/APSCC.2011.20.

Zhuang X., Cheng H., Xiong N.,Yang L. T. - Channel Assignment in Multi-Radio Wireless Networks Based on PSO Algorithm, 2010 5th International Conference on Future Information Technology, Busan. (2010) 1-6.DOI: 10.1109/ FUTURETECH.2010.5482773.

Chen Z., Chyu C. - An Evolutionary Algorithm with Multi–Local Search for the Resource-Constrained Project Scheduling Problem, Intelligent Information Management 2 (3) (2010) 220-226. DOI: 10.4236/iim.2012.23026

Das P. P., Acharyya S. - Simulated Annealing Variants for Solving Resource Constrained Project Scheduling Problem: A Comparative Study, Proceedings of 14th International Conference on Computer and Information Technology (2011) 469-474. DOI: 10.1109/ICCITechn.2011.6164835

Hosseinian, Amir H., Baradaran V. - 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 (2020) 2151-2176. DOI: 10.1007/s10489-020-01663-x

Hosseinian, Amir H., Baradaran V., Mahdi B. - Modeling of the time-dependent multi-skilled RCPSP considering learning effect. Journal of Modelling in Management 14 (3) (2019). DOI: 10.1108/JM2-07-2018-0098.

Nemati L. R., Hamed D. A., Hamid N. - Multi-mode resource constrained project scheduling and contractor selection: Mathematical formulation and metaheuristic algorithms, Applied Soft Computing 81 (2019) 105533. https://doi.org/ 10.1016/j.asoc.2019.105533

Younis M. T., Yang S. - Hybrid meta-heuristic algorithms for independent job scheduling in grid computing, Applied soft computing 72 (2018) 498-517. https://doi.org/10.1016/ j.asoc.2018.05.032

Tian Y., Xiong T., Liu Z., Mei Y, Wan L. - Multi-Objective multi-skill resource-constrained project scheduling problem with skill switches: Model and evolutionary approaches, Computers& Industrial Engineering 167 (C) (2022). DOI:https://doi.org/ 10.1016/j.cie.2021.107897.

Shima J., Behrouz A. N., Seyed T. A. N. - Preemptive Multi-skilled Resource Investment Project Scheduling Problem; Mathematical Modelling and Solution Approaches, Computers & Chemical Engineering 9 6(C) (2017) 55-68. DOI:10.1016/ j.compchemeng.2016.11.001

Najafzad H., Hamed D. A., Reza N. L. - Multi-skill project scheduling problem under time-of-use electricity tariffs and shift differential payments, Energy 168 (2019) 619-636.

Kennedy J., Eberhart R. - Particle swarm optimization, Neural Networks, 1995. Proceedings, IEEE International Conference 4 (1995) 1942-1948.

Zavala A. E. M. - EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation IIA Comparison, A Comparison Study of PSO Neighborhoods, Springer Verlag Berlin Heideberg, 251-295, ISBN 978-3-642-32725-4, 2013.

Shi Y., Eberhart R. - A modified particle swarm optimizer, IEEE World Congress on Computational Intelligence, Anchorage, AK, USA. (1998) 69-73. DOI:10.1109/ICEC. 1998.699146.

TNG Investment and Trading Joint Stock Company, 434/1 Bac Kan street - Thai Nguyen city, Viet Nam, Website http://www.tng.vn