Solving an Extended Resource Leveling Problem with Multiobjective Evolutionary Algorithms
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:63790", author = "Javier Roca and Etienne Pugnaghi and Gaëtan Libert", title = "Solving an Extended Resource Leveling Problem with Multiobjective Evolutionary Algorithms", 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.", volume = "2", number = "10", pages = "3598-12", }
