Abstract
In this paper we investigate and compare multi-objective and weighted single objective approaches to a real world workforce scheduling problem. For this difficult problem we consider the trade off in solution quality versus population diversity, for different sets of fixed objective weights. Our real-world workforce scheduling problem consists of assigning resources with the appropriate skills to geographically dispersed task locations while satisfying time window constraints. The problem is NP-Hard and contains the Resource Constrained Project Scheduling Problem (RCPSP) as a sub problem. We investigate a genetic algorithm and serial schedule generation scheme together with various multi-objective approaches. We show that multi-objective genetic algorithms can create solutions whose fitness is within 2% of genetic algorithms using weighted sum objectives even though the multi-objective approaches know nothing of the weights. The result is highly significant for complex real-world problems where objective weights are seldom known in advance since it suggests that a multi-objective approach can generate a solution close to the user preferred one without having knowledge of user preferences.
This work was funded by an EPSRC CASE Studentship in partnership with Vidus Ltd. (an @Road company).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Pinedo, M., Chao, X.: Operations scheduling with applications in manufacturing and services. McGraw-Hill, New York (1999)
Brucker, P., Knust, S.: Resource-Constrained Project Scheduling and Timetabling. In: Burke, E., Erben, W. (eds.) PATAT 2000. LNCS, vol. 2079, pp. 277–293. Springer, Heidelberg (2001)
Lova, A., Maroto, C., Thomas, P.: A multicriteria heuristic method to improve resource allocation in multiproject scheduling. Eur. J. Op. Res. 127, 408–424 (2000)
Holland, J.H.: Adaptation in Natural and Artificial Systems. University of Michigan Press, Michigan (1975)
Hartmann, S.: A Competitive Genetic Algorithm for Resource-Constrained Project Scheduling. Naval Research Logistics 45, 733–750 (1998)
Kolisch, R., Hartmann, S.: Experimental investigation of heuristics for resource-constrained project scheduling: An update. Eur. J. Op. Res (to appear, 2005)
Valls, V., Ballestin, F., Quintanilla, S.: A hybrid genetic algorithm for the RCPSP. Technical Report, Department of Statistics and Operations Research, University of Valencia (2005)
Schaffer, J.D.: Multiple Objective Optimization with Vector Evaluated Genetic Algorithms. In: Proceedings of an International Conference on Genetic Algorithms and their Applications, pp. 93–100 (1985)
Deb, K.: Multi-objective Optimisation using Evolutionary Algorithms. John Wiley and Sons, New York (2001)
Srinivas, N., Deb, K.: Multiobjective Optimisation Using Nondominated Sorting in Genetic Algorithms. J. Evolutionary Computation 2(3), 221–248 (1994)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A Fast and Elitist Multi-Objective Genetic Algorithm-NSGA-II. IEEE Trans. Evolutionary Computation 6, 849–858 (2002)
Zitzler, E., Thiele, L.: An evolutionary algorithm for multiobjective optimization: The strength pareto approach. Technical Report 43, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland (1998)
Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland (2001)
Corne, D.W., Knowles, J.D., Oates, M.J.: The pareto envelope-based selection algorithm for multiobjective optimisation. In: Deb, K., Rudolph, G., Lutton, E., Merelo, J.J., Schoenauer, M., Schwefel, H.-P., Yao, X. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 839–848. Springer, Heidelberg (2000)
Kolisch, R., Hartmann, S.: 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, pp. 147–178. Kluwer, Amsterdam (1999)
Landa Silva, J.D., Burke, E.K.: Using Diversity to Guide the Search in Multi-Objective Optimization. In: Coello Coello, C.A., Lamont, G.B. (eds.) Applications of Multi-Objective Evolutionary Algorithms, Advances in Natural Computation, vol. 1, pp. 727–751. World Scientific, Singapore (2004)
Shackelford, M., Corne, D.: Collaborative Evolutionary Multi-Project Resource Scheduling. In: Proceedings of the 2001 Congress on Evolutionary Computation, pp. 1131–1138. IEEE Press, Los Alamitos (2001)
Ernst, A.T., Jiang, H., Krishnamoorthy, M., Sier, D.: Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research 153, 3–27 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cowling, P., Colledge, N., Dahal, K., Remde, S. (2006). The Trade Off Between Diversity and Quality for Multi-objective Workforce Scheduling. In: Gottlieb, J., Raidl, G.R. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2006. Lecture Notes in Computer Science, vol 3906. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11730095_2
Download citation
DOI: https://doi.org/10.1007/11730095_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33178-0
Online ISBN: 978-3-540-33179-7
eBook Packages: Computer ScienceComputer Science (R0)