×

zbMATH — the first resource for mathematics

Minimizing shifts for personnel task scheduling problems: a three-phase algorithm. (English) Zbl 1304.90098
Summary: The personnel task scheduling problem is a subject of commercial interest which has been investigated since the 1950s. This paper proposes an effective and efficient three-phase algorithm for solving the shift minimization personnel task scheduling problem (SMPTSP). To illustrate the increased efficacy of the proposed algorithm over an existing algorithm, computational experiments are performed on a test problem set with characteristics motivated by employee scheduling applications. Experimental results show that the proposed algorithm outperforms the existing algorithm in terms of providing optimal solutions, improving upon most of the best-known solutions and revealing high-quality feasible solutions for those unsolved test instances in the literature.

MSC:
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ahuja, R. K.; Ergun, Ö.; Orlin, J. B.; Punnen, A. P., A survey of very large scale neighborhood search techniques, Discrete Applied Mathematics, 123, 75-102, (2002) · Zbl 1014.68052
[2] Akbari, M.; Zandieh, M.; Dorri, B., Scheduling part-time and mixed-skilled workers to maximize employee satisfaction, International Journal of Advanced Manufacturing Technology, 64, 1017-1027, (2013)
[3] Akjiratikarl, C.; Yenradee, P.; Drake, P. R., PSO-based algorithm for home care worker scheduling in the UK, Computers and Industrial Engineering, 53, 559-583, (2007)
[4] Alfares, H. K., Survey, categorization, and comparison of recent tour scheduling literature, Annals of Operations Research, 127, 145-175, (2004) · Zbl 1087.90023
[5] Al-Yakoob, S. M.; Sherali, H. D., A column generation approach for an employee scheduling problem with multiple shifts and work locations, Journal of the Operational Research Society, 59, 34-43, (2008) · Zbl 1167.90498
[6] Asensio-Cuesta, S.; Diego-Mas, J. A.; Canos-Daros, L.; Andres-Romano, C., A genetic algorithm for the design of job rotation schedules considering ergonomic and competence criteria, International Journal of Advanced Manufacturing Technology, 60, 1161-1174, (2012)
[7] Azaiez, M. N.; Al Sharif, S. S., A 0-1 goal programming model for nurse scheduling, Computers and Operations Research, 32, 491-507, (2005) · Zbl 1061.90042
[8] Baker, K. R., Workforce allocation in cyclical scheduling problems: A survey, Operational Research Quarterly, 27, 155-167, (1976)
[9] Bard, J. F.; Purnomo, H. W., Cyclic preference scheduling of nurses using a Lagrangian-based heuristic, Journal of Scheduling, 10, 5-23, (2007) · Zbl 1154.90410
[10] Beddoe, G. R.; Petrovic, S., Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering, European Journal of Operational Research, 175, 649-671, (2006) · Zbl 1142.90393
[11] Beliën, J.; Demeulemeester, E., On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem, Annals of Operations Research, 155, 143-166, (2007) · Zbl 1145.90017
[12] Bellanti, F.; Carello, G.; Della Croce, F.; Tadei, R., A greedy-based neighborhood search approach to a nurse rostering problem, European Journal of Operational Research, 153, 28-40, (2004) · Zbl 1053.90090
[13] Brucker, P.; Burke, E. K.; Curtois, T.; Qu, R.; Vanden Berghe, G., A shift sequence based approach for nurse scheduling and a new benchmark dataset, Journal of Heuristics, 16, 559-573, (2010) · Zbl 1230.90121
[14] Burke, E. K.; Curtois, T.; Post, G.; Qu, R.; Veltman, B., A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem, European Journal of Operational Research, 188, 330-341, (2008) · Zbl 1149.90346
[15] Burke, E. K.; Curtois, T.; Qu, R.; Vanden Berghe, G., A scatter search methodology for the nurse rostering problem, Journal of the Operational Research Society, 61, 1667-1679, (2010)
[16] Burke, E. K.; Curtois, T.; van Draat, L. F.; van Ommeren, J. K.; Post, G., Progress control in iterated local search for nurse rostering, Journal of the Operational Research Society, 62, 360-367, (2011)
[17] Burke, E. K.; De Causmaecker, P.; Vanden Berghe, G.; Van Landeghem, H., The state of the art of nurse rostering, Journal of Scheduling, 7, 441-499, (2004) · Zbl 1154.90422
[18] Burke, E. K.; Li, J. P.; Qu, R., A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems, European Journal of Operational Research, 203, 484-493, (2010) · Zbl 1177.90356
[19] Chakhlevitch, K.; Cowling, P., Choosing the fittest subset of low level heuristics in a hyperheuristic framework, Lecture Notes in Computer Science, 3448, 23-33, (2005) · Zbl 1101.90086
[20] Cipriano, R.; Di Gaspero, L.; Dovier, A., Hybrid approaches for rostering: A case study in the integration of constraint programming and local search, Lecture Notes in Computer Science, 4030, 110-123, (2006)
[21] Cordeau, J. F.; Laporte, G.; Pasin, F.; Ropke, S., Scheduling technicians and tasks in a telecommunications company, Journal of Scheduling, 13, 393-409, (2010) · Zbl 1231.90258
[22] Dantzig, G. B., Letter to the editor—A comment on edie’s “traffic delays at toll booths”, Operations Research, 2, 339-341, (1954)
[23] Di Gaspero, L.; Gärtner, J.; Kortsarz, G.; Musliu, N.; Schaerf, A.; Slany, W., The minimum shift design problem, Annals of Operations Research, 155, 79-105, (2007) · Zbl 1145.90019
[24] Dowling, D.; Krishnamoorthy, M.; Mackenzie, H.; Sier, D., Staff rostering at a large international airport, The Annals of Operations Research, 72, 125-147, (1997) · Zbl 0895.90137
[25] Edie, L. C., Traffic delays at toll booths, Operations Research, 2, 107-138, (1954)
[26] Eiselt, H. A.; Marianov, V., Employee positioning and workload allocation, Computers and Operations Research, 35, 513-524, (2008) · Zbl 1141.90465
[27] Eitzen, G.; Panton, D.; Mills, G., Multi-skilled workforce optimisation, Annals of Operations Research, 127, 359-372, (2004) · Zbl 1090.90077
[28] Elizondo, R.; Parada, V.; Pradenas, L.; Artigues, C., An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport, Journal of Heuristics, 16, 575-591, (2010) · Zbl 1230.90122
[29] Elshafei, M.; Alfares, H. K., A dynamic programming algorithm for days-off scheduling with sequence dependent labor costs, Journal of Scheduling, 11, 85-93, (2008) · Zbl 1168.90435
[30] Ernst, A. T.; Jiang, H.; Krishnamoorthy, M.; Owens, B.; Sier, D., An annotated bibliography of personnel scheduling and rostering, Annals of Operations Research, 127, 121-144, (2004) · Zbl 1090.90078
[31] 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) · Zbl 1053.90034
[32] Firat, M.; Hurkens, C. A.J., An improved MIP-based approach for a multi-skill workforce scheduling problem, Journal of Scheduling, 15, 363-380, (2012) · Zbl 1280.90044
[33] Fowler, J. W.; Wirojanagud, P.; Gel, E. S., Heuristics for workforce planning with worker differences, European Journal of Operational Research, 190, 724-740, (2008) · Zbl 1146.90486
[34] Goel, A.; Archetti, C.; Savelsbergh, M., Truck driver scheduling in Australia, Computers and Operations Research, 39, 1122-1132, (2012) · Zbl 1251.90148
[35] Goodman, M. D.; Dowsland, K. A.; Thompson, J. M., A grasp-knapsack hybrid for a nurse-scheduling problem, Journal of Heuristics, 15, 351-379, (2009) · Zbl 1180.90119
[36] Gunther, M.; Nissen, V., Particle swarm optimization and an agent-based algorithm for a problem of staff scheduling, Lecture Notes in Computer Science, 6025, 451-461, (2010)
[37] Gutjahr, W. J.; Rauner, M. S., An ACO algorithm for a dynamic regional nurse scheduling problem in Austria, Computers and Operations Research, 34, 642-666, (2007) · Zbl 1120.90019
[38] Hao, G.; Lai, K. K.; Tan, M., A neural network application in personnel scheduling, Annals of Operations Research, 128, 65-90, (2004) · Zbl 1056.90064
[39] He, F.; Qu, R., A constraint programming based column generation approach to nurse rostering problems, Computers and Operations Research, 39, 3331-3343, (2012) · Zbl 1349.90351
[40] Hertz, A.; Lahrichi, N.; Widmer, M., A flexible MILP model for multiple-shift workforce planning under annualized hours, European Journal of Operational Research, 200, 860-873, (2010) · Zbl 1177.90231
[41] Hochbaum, D. S.; Levin, A., Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms, Discrete Optimization, 3, 327-340, (2006) · Zbl 1112.90023
[42] Hojati, M.; Patil, A. S., An integer linear programming-based heuristic for scheduling heterogeneous, part-time service employees, European Journal of Operational Research, 209, 37-50, (2011) · Zbl 1208.90095
[43] Jacobs, L. W.; Brusco, M. J., A local-search heuristic for large set-covering problems, Naval Research Logistics, 42, 1129-1140, (1995) · Zbl 0839.90085
[44] Kohl, N.; Karisch, S. E., Airline crew rostering: problem types, modeling, and optimization, Annals of Operations Research, 127, 223-257, (2004) · Zbl 1087.90031
[45] Krishnamoorthy, M.; Ernst, A. T.; Baatar, D., Algorithms for large scale shift minimisation personnel task scheduling problems, European Journal of Operational Research, 219, 34-48, (2012) · Zbl 1244.90094
[46] Krishnamoorthy, M.; Ernst, A. T., The personnel task scheduling problem, (Yang, X.; Teo, K. L.; Caccetta, L., Optimisation methods and applications, (2001), Kluwer Dordrecht), 343-368 · Zbl 0978.90048
[47] Kroon, L. G.; Salomon, M.; Wassenhowe, L. N.V., Exact and approximation algorithms for the tactical fixed interval scheduling problem, Operations Research, 45, 624-638, (1997) · Zbl 0887.90089
[48] Laguna, M.; Casado, S.; Pacheco, J., Heuristical labour scheduling to optimize airport passenger flows, Journal of the Operational Research Society, 56, 649-658, (2005) · Zbl 1095.90034
[49] Laporte, G.; Pesant, G., A general multi-shift scheduling system, Journal of the Operational Research Society, 55, 1208-1217, (2004) · Zbl 1070.90056
[50] Lin, H. T.; Chen, Y. T.; Chou, T. Y.; Liao, Y. C., Crew rostering with multiple goals: an empirical study, Computers and Industrial Engineering, 63, 483-493, (2012)
[51] Lin, S. W.; Lee, Z. J.; Ying, K. C.; Lu, C. C., Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates, Computers and Operations Research, 38, 809-815, (2011) · Zbl 1202.90138
[52] Lucic, P.; Teodorovic, D., Metaheuristics approach to the aircrew rostering problem, Annals of Operations Research, 155, 311-338, (2007) · Zbl 1145.90025
[53] Maenhout, B.; Vanhoucke, M., An electromagnetic meta-heuristic for the nurse scheduling problem, Journal of Heuristics, 13, 359-385, (2007)
[54] Maenhout, B.; Vanhoucke, M., A hybrid scatter search heuristic for personalized crew rostering in the airline industry, European Journal of Operational Research, 206, 155-167, (2010) · Zbl 1188.90157
[55] Moz, M.; Pato, M. V., A genetic algorithm approach to a nurse rerostering problem, Computers and Operations Research, 34, 667-691, (2007) · Zbl 1120.90330
[56] Nissen, V.; Gunther, M., Staff scheduling with particle swarm optimisation and evolution strategies, Lecture Notes in Computer Science, 5482, 228-239, (2009)
[57] Ozcan, E., Memetic algorithms for nurse rostering, Lecture Notes in Computer Science, 3733, 482-492, (2005)
[58] Pisinger, D.; Ropke, S., Large neighborhood search, (Gendreau, M.; Potvin, J. Y., Handbook of metaheuristics, (2010), Springer New York), 399-419
[59] Pot, A.; Bhulai, S.; Koole, G., A simple staffing method for multiskill call centers, Manufacturing and Service Operations Management, 10, 421-428, (2008)
[60] Qu, R., & He, F. (2009). A hybrid constraint programming approach for nurse rostering problems. In SGAI International conference on innovative techniques and applications of artificial intelligence, Cambridge, England (pp. 211-224).
[61] Restrepo, M. I.; Lozano, L.; Medaglia, A. L., Constrained network-based column generation for the multi-activity shift scheduling problem, International Journal of Production Economics, 140, 466-472, (2012)
[62] Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177, 2033-2049, (2007) · Zbl 1110.90042
[63] Ruiz, R.; Stützle, T., An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, European Journal of Operational Research, 187, 1143-1159, (2008) · Zbl 1137.90514
[64] Schrimpf, G.; Schneider, J.; Stamm-Wilbrandt, H.; Dueck, G., Record breaking optimization results using the ruin and recreate principle, Journal of Computational Physics, 159, 139-171, (2000) · Zbl 0997.90105
[65] Seckiner, S. U.; Gokcen, H.; Kurt, M., An integer programming model for hierarchical workforce scheduling problem, European Journal of Operational Research, 183, 694-699, (2007) · Zbl 1175.90191
[66] Thompson, G. M.; Goodale, J. C., Variable employee productivity in workforce scheduling, European Journal of Operational Research, 170, 376-390, (2006) · Zbl 1085.90021
[67] Topaloglu, S.; Ozkarahan, I., An implicit goal programming model for the tour scheduling problem considering the employee work preferences, Annals of Operations Research, 128, 135-158, (2004) · Zbl 1056.90096
[68] Van den Bergh, J.; Beliën, J.; De Bruecker, P.; Demeulemeester, E.; De Boeck, L., Personnel scheduling: A literature review, European Journal of Operational Research, 226, 367-385, (2013) · Zbl 1292.90001
[69] Wright, P. D.; Bretthauer, K. M.; Cote, M. J., Reexamining the nurse scheduling problem: staffing ratios and nursing shortages, Decision Sciences, 37, 39-70, (2006)
[70] Yilmaz, E., A mathematical programming model for scheduling of nurses’ labor shifts, Journal of Medical Systems, 36, 491-496, (2012)
[71] Ying, K. C., Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic, International Journal of Advanced Manufacturing Technology, 38, 348-354, (2008)
[72] Ying, K. C., An iterated greedy heuristic for multistage hybrid flowshop scheduling problems with multiprocessor tasks, Journal of the Operational Research Society, 60, 810-817, (2009) · Zbl 1171.90412
[73] Ying, K. C., Scheduling identical wafer sorting parallel machines with sequence-dependent setup times using an iterated greedy heuristic, International Journal of Production Research, 50, 2710-2719, (2012)
[74] Ying, K. C.; Cheng, H. M., Dynamic parallel machine scheduling with sequence-dependent setup times using an iterated greedy heuristic, Expert Systems with Applications, 37, 2848-2852, (2010)
[75] Ying, K. C.; Gupta, J. N.D.; Lin, S. W.; Lee, Z. J., Permutation and non-permutation schedules for the flowline manufacturing cell with sequence dependent family setups, International Journal of Production Research, 48, 2169-2184, (2010) · Zbl 1197.90185
[76] Ying, K. C.; Liao, C. J., An ant colony system approach for scheduling problem, Production Planning and Control, 14, 68-75, (2003)
[77] Ying, K. C.; Liao, C. J., An ant colony system for permutation flow-shop sequencing, Computers and Operations Research, 31, 791-801, (2004) · Zbl 1048.90113
[78] Ying, K. C.; Lin, S. W.; Huang, C. Y., Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic, Expert Systems with Applications, 36, 7087-7092, (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.