Document Type : Original Article

Authors

Department of Industrial Engineering, Islamic Azad University, Tehran North Branch, Tehran, Iran.

Abstract

In this research, we study the multi-skill resource-constrained project scheduling problem, where there are generalized precedence relations between project activities. Workforces are able to perform one or several skills, and their efficiency improves by repeating their skills. For this problem, a mathematical formulation has been proposed that aims to optimize project completion time, reworking risks of activities, and costs of processing the activities, simultaneously. A modified version of the Pareto Archived Evolution Strategy (MV-PAES) is developed to solve the problem. Contrary to the basic PAES, this algorithm operates based on a population of solutions. For the proposed method, we devised crossover and mutation operators, which strengthen this algorithm in exploring solution space. Comprehensive numerical tests have been conducted to evaluate the performance of the MV-PAES in comparison with two other meta-heuristics. The outputs show the excellence of the MV-PAES in comparison with other methods. A real-world software development project has been studied to demonstrate the practicality of the proposed model for real-world environment. The influence of competency evolution has been investigated in this case study. The results imply that the competency evolution has a considerable impact on the objective function values.

Keywords

Afruzi, E., Najafi, A.A., Roghanian, E., and Mazinani, M., (2014). "A Multi-Objective Imperialist Competitive Algorithm for solving discrete time, cost and quality trade-off problems with mode-identity and resource-constrained situations", Computers & Operations Research, Vol. 50, pp. 80-96.
Afshar-Nadjafi, B., Rahimi, A., and Karimi, H., (2013). "A genetic algorithm for mode identity and the resource constrained project scheduling problem", Scientia Iranica, Vol. 20, No. 3, pp. 824-831.
Alcaraz, J., and Maroto, C., (2001). “A Robust Genetic Algorithm for Resource Allocation in Project Scheduling”, Annals of Operations Research, Vol. 102, No. 1-4, pp. 83-109.
Almeida, B.F., Correia, I., and Saldanha-da-Gama, F., (2016). "Priority-based heuristics for the multi-skill resource constrained project scheduling problem", Expert Systems with Applications, Vol. 57, pp. 91–103.
Bartusch, M., Mohring, R.H., and Radermacher, F.J., (1988). "Scheduling project networks with resource constraints and time windows", Annals of Operations Research, Vol. 16, pp. 201–240.
Bellenguez, O., and Néron, E., (2005). "Lower Bounds for the Multi-skill Project Scheduling Problem with Hierarchical Levels of Skills", In: Burke E., Trick M. (eds) Practice and Theory of Automated Timetabling V. PATAT 2004. Lecture Notes in Computer Science, vol 3616. Springer, Berlin, Heidelberg, pp. 229-243.
Bensmaine, A., Dahane, M., and Benyoucef, L., (2013). "A non-dominated sorting genetic algorithm based approach for optimal machines selection in reconfigurable manufacturing environment", Computers & Industrial Engineering, Vol. 66, No. 3, pp. 519-524.
Blazewicz, J., Lenstra, J.K., and Kan, A., (1983). "Scheduling subject to resource constraints: Classification and complexity", Discrete Applied Mathematics, Vol. 5, No.1, pp. 11-24.
Brucker, P., Drexl, A., Mohring, R., Neumann, K., and Pesch, E., (1999). "Resource-constrained project scheduling: notation, classification, models, and methods", European Journal of Operational Research, Vol. 112, No. 1, pp. 3-41.
Buddhakulsomsiri, J., and Kim, D.S., (2006). "Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting", European Journal of Operational Research, Vol. 175, pp. 279-295.
Chakrabortty, R.K., Sarker, R.A., and Essam, D.L., (2016). "Multi-mode resource-constrained project scheduling under resource disruptions", Computers & Chemical Engineering, Vol. 88, pp. 13-29.
Cheng, J., Fowler, J., Kempf, K., and Mason, S., (2015). "Multi-mode resource-constrained project scheduling Problems with non-preemptive activity splitting", Computers & Operations Research, Vol. 53, pp. 275-287.
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, Vol. 55, No. 21, pp. 6207-6234.
Cordeau, J., Laporte, G., Pasin, F., and Ropke, S., (2010). "Scheduling Technicians and Tasks in a Telecommunications Company", Journal of Scheduling, Vol. 13, No. 4, pp. 393-409.
Corne, D.W., Jerram, N.R., Knowles, J.D., and Oates, M.J., (2001). "PESA-II: region-based selection in evolutionary multi-objective optimization", In: Proceedings of the genetic and evolutionary computation conference (GECCO), pp. 283-290.
Corominas, A., Ojeda, J., Pastor, R., (2005). "Multi-objective allocation of multi-function workers with lower bounded capacity", Journal of the Operational Research Society, Vol. 56, No. 6, pp. 738-743.
Correia, I., Lourenco, L.L. and Saldanha-da-Gama, F., (2012), "Project scheduling with flexible resources: formulation and inequalities", OR Spectrum, Vol. 34 No. 3, pp. 635-663.
Correia, I., and Saldanha-da-Gama, F., (2014). "The impact of fixed and variable costs in a multi-skill project scheduling problem: An empirical study", Computers & Industrial Engineering, Vol. 72, pp. 230-238.
Dai, H., Cheng, W., and Guo, P., (2018). "An Improved Tabu Search for Multi-skill Resource-Constrained Project Scheduling Problems Under Step-Deterioration", Arabian Journal for Science and Engineering, Vol. 43, No. 6, pp. 3279-3290.
Deb, K., Agrawal, S., Pratap, A., and Meyarivan, T., (2000). "A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II", In: Schoenauer M. et al. (eds) Parallel Problem Solving from Nature PPSN VI. PPSN 2000. Lecture Notes in Computer Science, vol. 1917. Springer, Berlin, Heidelberg.
 
Deb, K., (2001). "Multi-objective optimization using evolutionary algorithms", Wiley, Hoboken, New York, USA, ISBN: 047187339X.
Gao, J., Chen, R., and Deng, W., (2013). "An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem", International Journal of Production Research, Vol. 51, No. 3, pp. 641-651.
Gomar, J., Haas, C., and Morton, D., (2002). "Assignment and Allocation Optimization of Partially Multi-skilled Workforce", Journal of Construction Engineering and Management, Vol. 128, No. 2, pp. 103-109.
Gutjahr, W.J., Katzensteiner, S., Reiter, P., Stummer, C., and Denk, M., (2008). "Competence-driven project portfolio selection, scheduling and staff assignment", Central European Journal of Operations Research, Vol. 16, No.3, pp. 281-306.
Hartmann, S., (2002). "A self-adapting genetic algorithm for project scheduling under resource constraints", Naval Research Logistics, Vol. 49, No.5, pp. 433-448.
Hartmann, S., (2013). "Project scheduling with resource capacities and requests varying with time: a case study", Flexible Services and Manufacturing Journal, Vol. 25, No. 1-2, pp. 74-93.
Hartmann, S. and Briskorn, D., (2010). "A survey of variants and extensions of the resource-constrained project scheduling problem", European Journal of Operational Research, Vol. 207, No. 3, pp. 1-14.
Ho, S., and Leung, J., (2010). "Solving a manpower scheduling problem for airline catering using metaheuristics", European Journal of Operational Research, Vol. 202, pp. 903-921.
Hosseinian, A.H., and Baradaran, V., (2019a). "Detecting communities of workforces for the multi-skill resource-constrained project scheduling problem: A dandelion solution approach", Journal of Industrial and Systems Engineering, Vol. 12, pp. 72-99.
Hosseinian, A.H., and Baradaran, V., (2019b). "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, Vol. 12, No. 2, pp. 155-178.
Hosseinian, A.H., and Baradaran, V., (2019c). "An Energy-efficient Mathematical Model for the Resource-constrained Project Scheduling Problem: An Evolutionary Algorithm", Iranian Journal of Management Studies, Vol. 12, No. 1, pp. 91-119.
Hosseinian, A.H., Baradaran, V., and Bashiri, M., (2019). "Modeling of the time-dependent multi-skilled RCPSP considering learning effect: An evolutionary solution approach", Journal of Modelling in Management, Vol. 14, No. 2, pp. 521-558.
Javanmard, S., Afshar-Nadjafi, B., and Niaki, S.T.A., (2016). "Preemptive multi-skilled resource investment project scheduling problem; mathematical modelling and solution approaches", Computers & Chemical Engineering, Vol. 96, pp. 55-68.
Kazemipoor, H., Tavakkoli-Moghaddam, R., Shahrezaei, P., and Azaron, A., (2013a). "A differential evolution algorithm to solve multi-skilled project portfolio scheduling problems", The International Journal of Advanced Manufacturing Technology, Vol. 64, No. 5-8, pp. 1099-1111.
Kazemipoor, H., Tavvakoli-Moghaddam, R., and Sharezaei, P., (2013b). "Solving a novel multi-skilled project scheduling model by scatter search", The South African Journal of Industrial Engineering, Vol. 24, No.1, pp. 121-135.
Knowles, J., and Corne, D., (1999). "The Pareto archived evolution strategy: a new baseline algorithm for Pareto multi-objective optimization", In: Proceedings of the 1999 Congress on Evolutionary Computation, IEEE, pp. 98-105, Washington, DC, USA.
Kolisch, R., and Hartmann, S., (1999). "Heuristic algorithms for solving the resource-constrained project scheduling problem: classification and computational analysis", In: Weglarz, J., ed. Project scheduling: recent models, algorithms and applications. New York: Kluwer Academic, pp. 147–178.
Kolisch, R., and Sprecher A., (1996). "PSPLIB - A project scheduling problem library", European Journal of Operational Research, Vol. 96, No. 1, pp. 205-216.
Laszczyk, M., and Myszkowski, P., (2019). "Improved selection in evolutionary multi–objective optimization of multi–skill resource–constrained project scheduling problem", Information Sciences, Vol. 481, pp. 412-431.
Li, H., and Womer, K., (2009). "Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm", Journal of Scheduling, Vol. 12, pp. 281-298.
Liu, S., and Wang C., (2012). "Optimizing linear project scheduling with multi-skilled crews", Automation in Construction, Vol. 24, pp. 16-23.
Maghsoudlou, H.R., Afshar-Nadjafi, B., and Niaki S.T.A., (2016). "A multi-objective invasive weeds optimization algorithm for solving multi-skill multi-mode resource constrained project scheduling problem", Computers & Chemical Engineering, Vol. 8, pp. 157-169.
Maghsoudlou, H.R., Afshar-Nadjafi, B., and 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, Vol. 54, pp. 46-61.
Mehmanchi, E., and Shadrokh S., (2013). "Solving a New Mixed Integer Non-Linear Programming Model of the Multi-Skilled Project Scheduling Problem Considering Learning and Forgetting Effect", In: Proceedings of the 2013 IEEE IEEM, Bangkok, Thailand.
Myszkowski, P., Skowronski, M., and Podlodowski, L., (2013). "Novel heuristic solutions for Multi–Skill Resource–Constrained Project Scheduling Problem", In: Proceedings of the 2013 Federated Conference on Computer Science and Information Systems, IEEE, pp. 159-166.
Myszkowski, P., Skowronski, M., Olech, L.P., and Oslizlo, K., (2015). "Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem", Soft Computing, Vol. 19, No. 12, pp. 3599-3619.
Myszkowski, P., Olech, L.P., Laszczyk, M., and Skowronski, M., (2018). "Hybrid Differential Evolution and Greedy Algorithm (DEGR) for solving Multi-Skill Resource-Constrained Project Scheduling Problem", Applied Soft Computing, Vol. 63, pp. 1-14.
Najafzad, H., Davari-Ardakani, H., and Nemati-Lafmejani, R., (2019). "Multi-skill project scheduling problem under time-of-use electricity tariffs and shift differential payments", Energy, Vol. 168, pp. 619-636.
Rahmati, S.H.A, Hajipour, V., and Niaki, S.T.A., (2013). "A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem", Applied Soft Computing, Vol. 13, pp. 1728-1740.
Schott, J.R., (1995). "Fault tolerant design using single and multi-criteria genetic algorithms optimization", Dissertation, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA.
 
Schwindt, C., and Zimmermann, J., (2015). "Handbook on Project Management and Scheduling Vol.1", Springer International Publishing Switzerland. https://doi.org/10.1007/978-3-319-05443-8.
Tabrizi, B.H., Tavvakoli-Moghaddam, R., and Ghaderi, S.F., (2014). "A two-phase method for a multi-skilled project scheduling problem with discounted cash flows", Scientia Iranica, Vol. 21, No. 3, pp. 1083-1095.
Tavana, M., Abtahi, A.R., and Khalili-Damghani, K., (2014). "A new multi-objective multi-mode model for solving preemptive time–cost–quality trade-off project scheduling problems", Expert Systems with Applications, Vol. 41, pp. 1830-1846.
Tirkolaee, E.B., Goli, A., Hematian, M., Kumar Sangaiah, A., and Han, T., (2019). "Multi-objective multi-mode resource constrained project scheduling problem using Pareto-based algorithms", Computing, Vol. 101, No. 6, pp. 547-570.
Valls, V., Perez, A., and Quintanilla, S., (2009). "Skilled workforce scheduling in Service Centers",European Journal of Operational Research, Vo. 193, No. 3, pp. 791-804.
Wang, L., and Zheng, X.L., (2018). "A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem", Swarm and Evolutionary Computation, Vol. 38, pp. 54-63.
Wu, M., and Sun, S., (2006). "A project scheduling and staff assignment model considering learning effect", The International Journal of Advanced Manufacturing Technology, Vol. 28, No. 11, pp. 1190-1195.
Zabihi, S., Rashidi Kahag, M., Maghsoudlou, H.R., and Afshar-Nadjafi, B., (2019). "Multi-objective teaching-learning-based meta-heuristic algorithms to solve multi-skilled project scheduling problem", Computers & Industrial Engineering, Vol. 136, pp. 195-211.
Zheng, H., Wang, L., and Zheng, X., (2015). "Teaching–learning-based optimization algorithm for multi-skill resource constrained project scheduling problem", Soft Computing, Vol. 21, No. 6, pp. 1537-1548.
Zitzler, E., and Thiele, L., (1998). "Multi-objective optimization using evolutionary algorithms — A comparative case study", In: Eiben A.E., Bäck T., Schoenauer M., Schwefel HP. (eds) Parallel Problem Solving from Nature — PPSN V. PPSN 1998. Lecture Notes in Computer Science, Vol. 1498. Springer, Berlin, Heidelberg.
Zitzler, E., (1999). "Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications", Dissertation, Swiss Federal Institute of Technology (ETH), Zürich, Switzerland.