Solving an Extended Resource Leveling Problem with Multiobjective Evolutionary Algorithms

Authors: Javier Roca, Etienne Pugnaghi, Gaëtan Libert

Abstract:

We introduce an extended resource leveling model that abstracts real life projects that consider specific work ranges for each resource. Contrary to traditional resource leveling problems this model considers scarce resources and multiple objectives: the minimization of the project makespan and the leveling of each resource usage over time. We formulate this model as a multiobjective optimization problem and we propose a multiobjective genetic algorithm-based solver to optimize it. This solver consists in a two-stage process: a main stage where we obtain non-dominated solutions for all the objectives, and a postprocessing stage where we seek to specifically improve the resource leveling of these solutions. We propose an intelligent encoding for the solver that allows including domain specific knowledge in the solving mechanism. The chosen encoding proves to be effective to solve leveling problems with scarce resources and multiple objectives. The outcome of the proposed solvers represent optimized trade-offs (alternatives) that can be later evaluated by a decision maker, this multi-solution approach represents an advantage over the traditional single solution approach. We compare the proposed solver with state-of-art resource leveling methods and we report competitive and performing results.

Keywords: Intelligent problem encoding, multiobjective decision making, evolutionary computing, RCPSP, resource leveling.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1083621

References:

[1] R. Kolisch., S. Hartmann, Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update, European Journal of Operational Research, 2005.
[2] J. Blazewicz, W. Cellary, R. Slowinsky, J. Weglarz . Scheduling under Resource Constraints: Deterministic Models, Annals of Operations Research, 1987.
[3] R. Kolisch, S. Hartmann. Heuristic Algorithms for Solving the Resource-Constrained Project Scheduling Problem: Classification and Computational Analysis in Project scheduling: Recent models, algorithms and applications, Kluwer, 1999.
[4] P. Brucker, S. Knust, Complex Scheduling, Springer, 2005.
[5] V. Valls, F. Ballestín, S. Quintanilla, Justification Technique Generalizations, in Perspectives in Modern Project Scheduling, Springer, 2006.
[6] H.N. Ahuja, Construction Performance Control by Networks, Wiley, New York, 1976.
[7] M.A. Younis, B. Saad, Optimal resource leveling of multi-resource projects, Computers and Industrial Engineering, 31, 1996.
[8] A.R. Burgess, J.B. Killebrew, Variation in activity level on a cyclical arrow diagram, Journal of Industrial Engineering 13, 1962.
[9] R.B. Harris, Precedence and Arrow Networking Techniques for Construction, Wiley, New York, 1978.
[10] R.B. Harris, Packing method for resource leveling (pack), Journal of Construction Engineering and Management 116, 1990.
[11] L. Kim, K. Kim, N. Jee, Y. Yoon, Enhanced Resource Leveling technique for Project Scheduling, Journal of Asian Architecture and Building Engineering, 466, 2005
[12] P. Brucker, A. Drexl, W. Mohring, K. Neumann, E. Pesh, Resourceconstrained project scheduling: Notation, classification, models, and methods, European Journal of Operational Research 112, 3-41, 1999.
[13] Leu, C. Yang, J. Huang, Resource leveling in construction by genetic algorithm-based optimization and its decision support system application, Automation in construction, 2000.
[14] Y. Sheng-Li, M. Hong, L. Ri, GA-Based Resource Leveling Optimization for Construction Project, in International Conference on Machine Learning and Cybernetics, 2006
[15] X. Li, L. Zhang, J. Qi, S. Zhang, An extended particle swarm optimization algorithm based on coarse-grained and fine-grained criteria an dits application, Journal of Central South University of Technology, 15, 2008.
[16] K. Raja, S. Kumanan, Resource Leveling Using Petrinet and Memetic Approach, American Journal of Applied Sciences, 4, 2007.
[17] P. Dasgupta. P. Chakrabarti, S. Desarkar, Multiobjective Heuristic Search: An introduction to Intelligent Search Methods for Multicriteria Optimization, Computational Intelligence, Vieweg, 1999.
[18] C. Coello, D. Van Veldhuizen, G. Lamont, Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic Publishers, 2002.
[19] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2002.
[20] J. Alcaraz, C. Maroto, A hybrid genetic algorithm based on intelligent encoding for project scheduling, in perspectives in modern project scheduling, Springer, 2007.
[21] V. Valls, F. Ballestin,S. Quintanilla S, A hybrid genetic algorithm for the resource-costrained scheduling problem, European Journal of Operational Research, 2007.
[22] E. Demeulemeester, W. Herroelen, Project scheduling. A research handbook, Kluwer Academic Publishers, 2002.
[23] J. Durillo, A Nebro, F. Luna, B. Dorronsoro , E. Alba, jMetal: A Java Framework for Developing Multi-Objective Optimization Metaheuristics, Tech Report DNL06, Departamento de Lenguajes y Ciencias de la Computación, University of Málaga, 2006.
[24] J. Roca, F. Bossuyt, G. Libert, PSPSolver: An Open Source Library for the RCPSP, Proceedings of the 26th Workshop of the UK Planning and Scheduling Special Interest Group, 2007.
[25] R. Kolish, A. Sprechher, PSPLIB A Project Scheduling Problem Library, European Journal of Operational Research, 96, 1997.