A Harmony Search Algorithm for Multi-Skilled Rcpsp with Time-Dependent Resource Capacities

Document Type : Original Article

Authors

1 PhD. student, Faculty of Engineering, Islamic Azad University, Tehran North Branch, Tehran, Iran.

2 Assistant Professor, Faculty of Engineering, Islamic Azad University, Tehran North Branch, Tehran, Iran.

3 Professor, Faculty of Engineering, Shahed University, Tehran, Iran.

Abstract

In this paper, we address the multi-skilled RCPSP with time-dependent resource capacities and generalized precedence relations between activities. In this problem, a set of multi-skilled workforces are required to execute project activities. Each worker is able to perform several skills. The availability of workforces is time-dependent due to holidays, weekends, sicknesses, etc. Therefore, in this study, a mathematical formulation is proposed for the multi-skilled RCPSP with time-dependent resource availabilities. The objective function of the model is minimization of project completion time. The proposed model in this study is an NP-Hard problem in the strong sense. Hence, we develop a new meta-heuristic algorithm based on harmony search algorithm to solve the proposed model. New crossover and mutation operators have been designed for the proposed method to produce diverse solutions and to prevent the proposed algorithm from converging to a local optima. Hence, the proposed method not only uses the common procedure in harmony search algorithm, but also it employs the proposed crossover and mutation operators to explore solution space more accurately. The generated solutions are all combined and the harmony memory is updated. The effectiveness of this method has been compared to particle swarm optimization (PSO) and genetic algorithm (GA) in solving 30 test problems. The results show that the proposed method has been superior in terms of multiple performance measures.

Keywords

References

[1]    Hartmann, S., & Briskorn, D., (2010). A survey of variants and extensions of the resource-constrained project scheduling problem, European Journal of Operational Research, 207(1), 1-14.
[2]    Blazewicz, J., Lenstra, J.K. & Kan, A., (1983). Scheduling subject to resource constraints: Classification and complexity, Discrete Applied Mathematics, 5(1), 11-24.
[3]    Shahbazi, S., Sajjadi, S.M., & Jolai, F., (2018). A Simulation-Based Optimization Model for Determining the Sequence of Implementing Projects Related To New Product Development, Modern Researches in Decision Making, 2(4), 129-152.
[4]    Chen, J., Fowler, J., Kempf, K., & Mason, S., (2015). Multi-mode resource-constrained project scheduling Problems with non-preemptive activity splitting, Computers & Operations Research, 53(2), 275-287.
[5]    Hartmann, S., (2013). Project scheduling with resource capacities and requests varying with time: a case study, Flexible Services and Manufacturing Journal, 25(1), 74-93.
[6]    Néron, E., & Baptista, D., (2002). Heuristics for multi-skill project scheduling problem, International Symposium on combinatorial optimization (CO’2002), Paris, France.
[7]    Ghafoori, S., & Taghizadeh Yazdi, M.R., (2017). Proposing a Multi-Objective Mathematical Model for RCPSP and Solving It with Firefly and Simulated Annealing algorithms, Modern Researches in Decision Making, 1(4), 117-142.
[8]    Maghsoudlou, H.M., Nadjafi, B., & Niaki, S.T.A., (2017). Multi-skilled project scheduling with level-dependent rework risk; three multi-objective mechanisms based on cuckoo search, Applied Soft Computing, 54, 46-61.
[9]    Lee, K. S. & Geem, Z. W., (2005). A New Meta-Heuristic Algorithm for Continuous Engineering Optimization: Harmony Search Theory and Practice, Computer Methods in Applied Mechanics and Engineering, 194, 3902-3933.
[10]  Rastgar, I., & Sahraeian, R., (2013). Developing harmony search algorithm for solving optimization problems: a case study in parallel machine production scheduling problem, Journal of Industrial Engineering Research in Production Systems, 1(1), 57-71.
[11]  Bartusch, M., Mohring, R.H., & Radermacher, F.J., (1988). Scheduling project networks with resource constraints and time windows, Annals of Operations Research, 16(1), 201–240.
[12]  Sprecher, A., (1994). Resource-constrained project scheduling: exact methods for the multi-mode case, Number 409 in lecture notes in economics and mathematical systems. Springer, Berlin, DOI: 10.1007/978-3-642-48397-4.
[13]  Buddhakulsomsiri, J., & Kim, D.S., (2006). Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting, European Journal of Operational Research, 175(1), 279-295.
[14]  Ho, S., & Leung, J., (2010). Solving a manpower scheduling problem for airline catering using metaheuristics, European Journal of Operational Research, 202(3), 903-921.
[15]  Cordeau, J., Laporte, G., Pasin, F., & Ropke, S., (2010). Scheduling Technicians and Tasks in a Telecommunications Company, Journal of Scheduling, 13(4), 393-409.
[16]  Liu, S., & Wang, C., (2012). Optimizing linear project scheduling with multi-skilled crews, Automation in Construction, 24, 16-23.
[17]  Kazemipoor, H., Tavakkoli-Moghaddam, R., Shahnazari-Shahrezaei, P., & Azaron, A., (2013). A differential evolution algorithm to solve multi-skilled project portfolio scheduling problems, The International Journal of Advanced Manufacturing Technology, 64(5-8), 1099-1111.
[18]  Myszkowski, P.B, & Skowronski, M., (2013). Specialized genetic operators for multi skill resource-constrained project scheduling problem, 19th International Conference on Soft Computing MENDEL, 57-62.
[19]  Mehmanchi, E., & Shadrokh, S., (2013). Solving a New Mixed Integer Non-Linear Programming Model of the Multi-Skilled Project Scheduling Problem Considering Learning and Forgetting Effect, Proceedings of the 2013 IEEE IEEM, Bangkok, Thailand.
[20]  Kazemipoor, H., Tavvakoli-Moghaddam, E., & Sharezaei, P., (2013). Solving a novel multi-skilled project scheduling model by scatter search, South African Journal of Industrial Engineering, 24(1), 121-135.
[21]  Tabrizi, B.H., Tavvakoli-Moghaddam, R., & Ghaderi, S.F., (2014). A two-phase method for a multi-skilled project scheduling problem with discounted cash flows, Scientia Iranica, 21(3), 1083-1095.
[22]  Zheng, H., Wang, L., & Zheng, X., (2015). Teaching–learning-based optimization algorithm for multiskill resource constrained project scheduling problem, Soft Computing, 21(6), 1537-1548.
[23]  Javanmard, S., Nadjafi, B., & Niaki, S.T.A., (2016). Preemptive multi-skilled resource investment project scheduling problem; mathematical modelling and solution approaches, Computers and Chemical Engineering, 96(1), 55-68.
[24]  Maghsoudlou, H.M., Nadjafi, B., & Niaki, S.T.A., (2016). A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem, Computers and Chemical Engineering, 8(1), 157-169.
[25]  Chen, R., Liang, C., Gu, D., and Leung, J., (2017). A multi-objective model for multi-project scheduling and multi-skilled staff assignment for IT product development considering competency evolution, International Journal of Production Research, 55(21), 1-29.
[26]  Geem, Z.W., Kim J.H. & Loganathan G.V. (2001). A new heuristic optimization algorithm: harmony search. Simulations, 76, 60–68.
[27]  Kalivarapu, J., Jain, S., & Bag, S., (2015). An improved harmony search algorithm with dynamically varying bandwidth, Engineering Optimization, 48(7), 1091-1108.
[28]  Wang, L., Pan, Q.K., & Tasgetiren, M.F., (2011). A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem, Computers & Industrial Engineering, 61(1), 76–83.
[29]  Bagher, M., Kassaee, M., Allam Tabriz, A., & Zandieh, M., (2018). Truck Scheduling in Distribution Systems with Multiple Cross Docks and No Intermediate Storage, Modern Researches in Decision Making, 2(4), 1-27.
[30]  Mahdavi, A.M., (2007). Designing Quality Measurement Model of Information System Services Based on Genetic Algorithm, Management Research in Iran, 11(20), 235-263.
[31]  Asadi, R., Kazemzadeh, R., Nakhaei Kamal Abadi, I., & Bagherinejad, Z., (2013). A Joint Ordering Model for Automotive parts in Two-level Supply Chain, Management Research in Iran, 17(2), 1-18.

Files

Share

How to cite

Statistics