Weitere Artikel dieser Ausgabe durch Wischen aufrufen
Staff assignment is a compelling exercise that affects most companies and organizations in the service industries. Here, we introduce a new real-world staff assignment problem that was reported to us by a Swiss provider of commercial employee scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of critical and noncritical requests, including employees’ personal preferences. Each request has a target value, and deviations from the target value are associated with integer acceptance levels. These acceptance levels reflect the relative severity of possible deviations, e.g., for the request of an employee to have at least two weekends off, having one weekend off is preferable to having no weekend off and thus receives a higher acceptance level. The objective is to minimize the total number of deviations in lexicographical order of the acceptance levels. Staff assignment approaches from the literature are not applicable to this problem. We provide a binary linear programming formulation and propose a matheuristic for large-scale instances. The matheuristic employs effective strategies to determine the subproblems and focuses on finding good feasible solutions to the subproblems rather than proving their optimality. Our computational analysis based on real-world data shows that the matheuristic scales well and outperforms commercial employee scheduling software.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Aickelin, U., & Dowsland, K. (2000). Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem. Journal of Scheduling, 3(3), 139–153. CrossRef
Aickelin, U., & Dowsland, K. A. (2004). An indirect genetic algorithm for a nurse-scheduling problem. Computers and Operations Research, 31(5), 761–778. CrossRef
Al-Yakoob, S., & Sherali, H. (2007). Mixed-integer programming models for an employee scheduling problem with multiple shifts and work locations. Annals of Operations Research, 155(1), 119–142. CrossRef
Azaiez, M. N., & Al Sharif, S. (2005). A 0–1 goal programming model for nurse scheduling. Computers and Operations Research, 32(3), 491–507. CrossRef
Bai, R., Burke, E. K., Kendall, G., Li, J., & McCollum, B. (2010). A hybrid evolutionary approach to the nurse rostering problem. IEEE Transactions on Evolutionary Computation, 14(4), 580–590. CrossRef
Ball, M. O. (2011). Heuristics based on mathematical programming. Surveys in Operations Research and Management Science, 16(1), 21–38. CrossRef
Bard, J. F., & Wan, L. (2006). The task assignment problem for unrestricted movement between workstation groups. Journal of Scheduling, 9(4), 315–341. CrossRef
Beaulieu, H., Ferland, J. A., Gendron, B., & Michelon, P. (2000). A mathematical programming approach for scheduling physicians in the emergency room. Health Care Management Science, 3(3), 193–200. CrossRef
Berrada, I., Ferland, J. A., & Michelon, P. (1996). A multi-objective approach to nurse scheduling with both hard and soft constraints. Socio-Economic Planning Sciences, 30(3), 183–193. CrossRef
Bertels, S., & Fahle, T. (2006). A hybrid setup for a hybrid scenario: Combining heuristics for the home health care problem. Computers and Operations Research, 33(10), 2866–2890. CrossRef
Bester, M., Nieuwoudt, I., & Van Vuuren, J. H. (2007). Finding good nurse duty schedules: A case study. Journal of Scheduling, 10(6), 387–405. CrossRef
Bixby, R. E. (2012). A brief history of linear and mixed-integer programming computation. Documenta Mathematica, Extra Volume: Optimization Stories, 107–121.
Boschetti, M. A., Maniezzo, V., Roffilli, M., & Bolufé Röhler, A. (2009). Matheuristics: Optimization, simulation and control. In M. J. Blesa, C. Blum, L. Di Gaspero, A. Roli, M. Sampels, & A. Schaerf (Eds.), Hybrid metaheuristics: 6th international workshop on hybrid metaheuristics (pp. 171–177). Heidelberg: Springer.
Chang, C. T. (2006). Mixed binary interval goal programming. Journal of the Operational Research Society, 57, 469–473. CrossRef
Chang, C. T., & Lin, T. C. (2009). Interval goal programming for s-shaped penalty function. European Journal of Operational Research, 199, 9–20. CrossRef
Charnes, A., & Collomb, B. (1972). Optimal economic stabilization policy: Linear goal-interval programming models. Socio-Economic Planning Sciences, 6(4), 431–435. CrossRef
Charnes, A., Cooper, W. W., & Ferguson, R. O. (1955). Optimal estimation of executive compensation by linear programming. Management Science, 1, 138–151. CrossRef
Charnes, A., Cooper, W. W., Harrald, J., Karwan, K. R., & Wallace, W. A. (1976). A goal interval programming model for resource allocation in a marine environmental protection program. Journal of Environmental Economics and Management, 3, 347–362. CrossRef
Cordeau, J. F., Gendreau, M., Laporte, G., Potvin, J. Y., & Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society, 53, 512–522. CrossRef
Cordeau, J. F., Laporte, G., Pasin, F., & Ropke, S. (2010). Scheduling technicians and tasks in a telecommunications company. Journal of Scheduling, 13(4), 393–409. CrossRef
De Bruecker, P., Van den Bergh, J., Beliën, J., & Demeulemeester, E. (2015). Workforce planning incorporating skills: State of the art. European Journal of Operational Research, 243(1), 1–16. CrossRef
Della Croce, F., & Salassa, F. (2014). A variable neighborhood search based matheuristic for nurse rostering problems. Annals of Operations Research, 218(1), 185–199. CrossRef
Dowsland, K. A. (1998). Nurse scheduling with tabu search and strategic oscillation. European Journal of Operational Research, 106(2), 393–407. CrossRef
Eiselt, H. A., & Marianov, V. (2008). Employee positioning and workload allocation. Computers and Operations Research, 35(2), 513–524. CrossRef
Ernst, A. T., Jiang, H., Krishnamoorthy, M., Owens, B., & Sier, D. (2004). An annotated bibliography of personnel scheduling and rostering. Annals of Operations Research, 127(1–4), 21–144. CrossRef
Falasca, M., Zobel, C., & Ragsdale, C. (2011). Helping a small development organization manage volunteers more efficiently. Interfaces, 41(3), 254–262. CrossRef
Fischetti, M., & Lodi, A. (2003). Local branching. Mathematical Programming, 98(1–3), 23–47. CrossRef
Ignizio, J. (2004). Optimal maintenance headcount allocation: An application of Chebyshev goal programming. International Journal of Production Research, 42(1), 201–210. CrossRef
Jones, D., & Tamiz, M. (1995). Expanding the flexibility of goal programming via preference modelling techniques. Omega, 23(1), 41–48. CrossRef
Jones, D., & Tamiz, M. (2010). Goal programming variants. In Practical goal programming (pp. 11–22). Boston, MA: Springer US. doi: 10.1007/978-1-4419-5771-9_2.
Jones, D., & Tamiz, M. (2016). A review of goal programming. In S. Greco, M. Ehrgott, & J. R. Figueira (Eds.), Multiple criteria decision analysis: State of the art surveys (pp. 903–926). New York: Springer. CrossRef
Jones, D. F., & Tamiz, M. (2002). Goal programming in the period 1990–2000. In M. Ehrgott & X. Gandibleux (Eds.), Multiple criteria optimization—State of the art annotated bibliographic surveys. Dordrecht: Kluwer Academic Publishers.
Jones, D. F., Mirrazavi, S. K., & Tamiz, M. (2002). Multi-objective meta-heuristics: An overview of the current state-of-the-art. European Journal of Operational Research, 137(1), 1–9. CrossRef
Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R. E., et al. (2011). MIPLIB 2010. Mathematical Programming Computation, 3(2), 103–163. CrossRef
Kopanos, G. M., Méndez, C. A., & Puigjaner, L. (2010). MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry. European Journal of Operational Research, 207(2), 644–655. CrossRef
Kvanli, A. H. (1980). Financial planning using goal programming. Omega, 8, 207–218. CrossRef
Lodi, A. (2010). Mixed integer programming computation. In M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, & L. A. Wolsey (Eds.), 50 years of integer programming 1958–2008: From the early years to the state-of-the-art (pp. 619–645). Heidelberg: Springer.
Louly, M. A. O. (2013). A goal programming model for staff scheduling at a telecommunications center. Journal of Mathematical Modelling and Algorithms in Operations Research, 12(2), 167–178. CrossRef
Maenhout, B., & Vanhoucke, M. (2008). Comparison and hybridization of crossover operators for the nurse scheduling problem. Annals of Operations Research, 159(1), 333–353. CrossRef
Maniezzo, V., Stützle, T., & Voss, S. (2009). Matheuristics: Hybridizing metaheuristics and mathematical programming. New York: Springer.
Mihaylov, M., Smet, P., Van Den Noortgate, W., & Vanden Berghe, G. (2016). Facilitating the transition from manual to automated nurse rostering. Health Systems, 5(2), 120–131. CrossRef
Parr, D., & Thompson, J. M. (2007). Solving the multi-objective nurse scheduling problem with a weighted cost function. Annals of Operations Research, 155(1), 279–288. CrossRef
Raidl, G. R., & Puchinger, J. (2008). Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization. In C. Blum, M. J. B. Aguilera, A. Roli, & M. Sampels (Eds.), Hybrid metaheuristics: An emerging approach to optimization (pp. 31–62). Heidelberg: Springer. CrossRef
Rihm, T., & Baumann, P. (2015a). Improving fairness in staff assignment: An approach for lexicographic goal programming. In T. Magnanti, K. Chai, R. Jiao, S. Chen, & M. Xie (Eds.), Proceedings of the 2015 IEEE international conference on industrial engineering and engineering management, Singapore (pp. 1247–1251).
Rihm, T., & Baumann, P. (2015b). A lexicographic goal programming approach for staff assignment with acceptance levels. In Z. Hanzálek, G. Kendall, B. McCollum, & P. Šůcha (Eds.), Proceedings of the 7th multidisciplinary international conference on scheduling: Theory and applications, Prague (pp. 526–540).
Romero, C. (2004). A general structure of achievement function for a goal programming model. European Journal of Operational Research, 153, 675–686. CrossRef
Romero, C. (2014). Handbook of critical issues in goal programming. Oxford: Pergamon Press.
Smet, P., & Vanden Berghe, G. (2012). A matheuristic approach to the shift minimisation personnel task scheduling problem. In D. Kjenstad, A. Riise, T. E. Nordlander, B. McCollum, & Burke (Eds.). Proceedings of the 9th international conference on the practice and theory of automated timetabling, Son (pp. 145–160).
Smet, P., Bilgin, B., De Causmaecker, P., & Vanden Berghe, G. (2014a). Modelling and evaluation issues in nurse rostering. Annals of Operations Research, 218(1), 303–326. CrossRef
Smet, P., Wauters, T., Mihaylov, M., & Vanden Berghe, G. (2014b). The shift minimisation personnel task scheduling problem: A new hybrid approach and computational insights. Omega, 46, 64–73. CrossRef
Tamiz, M., Jones, D. F., & El-Darzi, E. (1995). A review of goal programming and its applications. Annals of Operations Research, 58, 39–53. CrossRef
Topaloglu, S. (2006). A multi-objective programming model for scheduling emergency medicine residents. Computers and Industrial Engineering, 51(3), 375–388. CrossRef
Valls, V., Pérez, Á., & Quintanilla, S. (2009). Skilled workforce scheduling in service centres. European Journal of Operational Research, 193(3), 791–804. CrossRef
Van den Bergh, J., Belïen, J., De Bruecker, P., & Demeulemeester, E. (2013). Personnel scheduling: A literature review. European Journal of Operational Research, 226, 367–385. CrossRef
- Staff assignment with lexicographically ordered acceptance levels
- Springer US
Neuer Inhalt/© Stellmach, Neuer Inhalt/© Maturus, Pluta Logo/© Pluta, digitale Transformation/© Maksym Yemelyanov | Fotolia