# zbMATH — the first resource for mathematics

The minimum shift design problem. (English) Zbl 1145.90019
Summary: The min-Shift Design problem (MSD) is an important scheduling problem that needs to be solved in many industrial contexts. The issue is to find a minimum number of shifts and the number of employees to be assigned to these shifts in order to minimize the deviation from workforce requirements. Our research considers both theoretical and practical aspects of the min-Shift Design problem. This problem is closely related to the minimum edge-cost flow problem (MECF), a network flow variant that has many applications beyond shift scheduling. We show that MSD reduces to a special case of MECF and, exploiting this reduction, we prove a logarithmic hardness of approximation lower bound for MSD. On the basis of these results, we propose a hybrid heuristic for the problem, which relies on a greedy heuristic followed by a local search algorithm. The greedy part is based on the network flow analogy, and the local search algorithm makes use of multiple neighborhood relations. An experimental analysis on structured random instances shows that the hybrid heuristic clearly outperforms our previous commercial implementation. Furthermore, it highlights the respective merits of the composing heuristics for different performance parameters.

##### MSC:
 90B35 Deterministic scheduling theory in operations research 90C59 Approximation methods and heuristics in mathematical programming
##### Software:
DIMACS; EasyLocal++; PPRN; Tabu search
Full Text:
##### References:
 [1] Aarts, E., & Lenstra, J. K. (Eds.). (1997). Local search in combinatorial optimization. New York: Wiley. · Zbl 0869.00019 [2] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows, Englewood Cliffs: Prentice-Hall. · Zbl 1201.90001 [3] Balakrishnan, N., & Wong, R. T. (1990). A network model for the rotating workforce scheduling problem. Networks, 20, 25–42. · doi:10.1002/net.3230200103 [4] Bar-Ilan, J., Kortsarz, G., & Peleg, D. (2001). Generalized submodular cover problems and applications. Theoretical Computer Science, 250(12), 179–200. · Zbl 0952.68063 · doi:10.1016/S0304-3975(99)00130-9 [5] Bartholdi, J., Orlin, J., & Ratliff, H. (1980). Cyclic scheduling via integer programs with circular ones. Operations Research, 28, 110–118. · Zbl 0451.90075 · doi:10.1287/opre.28.5.1074 [6] Burke, E. K., De Causmaeker, P., Vanden Berghe, G., & Van Landeghem, H. (2004). The state of the art of nurse rostering. Journal of Scheduling, 7, 441–499. · Zbl 1154.90422 · doi:10.1023/B:JOSH.0000046076.75950.0b [7] Castro, J., & Nabona, N. (1996). An implementation of linear and nonlinear multicommodity network flows. European Journal of Operational Research, 92, 37–53. · Zbl 0912.90125 · doi:10.1016/0377-2217(95)00137-9 [8] Di Gaspero, L., & Schaerf, A. (2003). EasyLocal++: an object-oriented framework for flexible design of local search algorithms. Software Practice & Experience, 33(8), 733–765. · Zbl 01963260 · doi:10.1002/spe.524 [9] Di Gaspero, L., & Schaerf, A. (2006). Neighborhood portfolio approach for local search applied to timetabling problems. Journal of Mathematical Modeling and Algorithms, 5(1), 65–89. · Zbl 1103.90102 · doi:10.1007/s10852-005-9032-z [10] Garey, M. R., & Johnson, D. S. (1979). Computers and intractability–a guide to NP-completeness. San Francisco: W.H. Freeman. · Zbl 0411.68039 [11] Gärtner, J., Musliu, N., & Slany, W. (2001). Rota: a research project on algorithms for workforce scheduling and shift design optimization. AI Communications: The European Journal on Artificial Intelligence, 14(2), 83–92. · Zbl 0995.68009 [12] Glover, F., & Laguna, M. (1997). Tabu search. Dordrecht: Kluwer Academic. ISBN 0-7923-9965-X. · Zbl 0930.90083 [13] Glover, F., & McMillan, C. (1986). The general employee scheduling problem: an integration of MS and AI. Computers & Operations Research, 13(5), 563–573. · doi:10.1016/0305-0548(86)90050-X [14] Goldberg, A. V. (1997). An efficient implementation of a scaling minimum-cost flow algorithm. Journal of Algorithms, 22, 1–29. · Zbl 05473508 · doi:10.1006/jagm.1995.0805 [15] Hochbaum, D. (2000). Optimization over consecutive 1’s and circular 1’s constraints. Unpublished manuscript. [16] Hoos, H. H., & Stützle, T. (1999). Towards a characterisation of the behaviour of stochastic local search algorithms for SAT. Artificial Intelligence, 112, 213–232. · Zbl 0996.68069 · doi:10.1016/S0004-3702(99)00048-X [17] Hoos, H. H., & Stützle, T. (2005). Stochastic local search: foundations and applications. San Francisco: Morgan Kaufmann. ISBN 1-55860-872-9. · Zbl 1126.68032 [18] Jackson, W. K., Havens, W. S., & Dollard, H. (1997). Staff scheduling: a simple approach that worked (Technical report CMPT97-23). Intelligent Systems Lab, Centre for Systems Science, Simon Fraser University. Available at http://citeseer.nj.nec.com/101034.html . [19] Johnson, D. S. (2002). A theoretician’s guide to the experimental analysis of algorithms. In M. H. Goldwasser, D. S. Johnson, & C. C. McGeoch (Eds.), Data structures, near neighbor searches, and methodology: fifth and sixth DIMACS implementation challenges (pp. 215–250). American Mathematical Society. URL http://www.research.att.com/$$\sim$$dsj/papers/experguide.ps . [20] Krumke, S. O., Noltemeier, H., Schwarz, S., Wirth, H.-C., & Ravi, R. (1998). Flow improvement and network flows with fixed costs. In Proceedings of the international conference on operations research (OR-98), Zürich, Switzerland. · Zbl 0965.90006 [21] Lau, H. C. (1996). On the complexity of manpower scheduling. Computers & Operations Research, 23(1), 93–102. · Zbl 0838.90065 · doi:10.1016/0305-0548(94)00094-O [22] Musliu, N., Gärtner, J., & Slany, W. (2002). Efficient generation of rotating workforce schedules. Discrete Applied Mathematics, 118(12), 85–98. · Zbl 0995.90034 · doi:10.1016/S0166-218X(01)00258-X [23] Musliu, N., Schaerf, A., & Slany, W. (2004). Local search for shift design. European Journal of Operational Research, 153(1), 51–64. · Zbl 1053.90043 · doi:10.1016/S0377-2217(03)00098-5 [24] Papadimitriou, C. H., & Steiglitz, K. (1982). Combinatorial optimization: algorithms and complexity. Englewood Cliffs: Prentice-Hall. · Zbl 0503.90060 [25] Raz, R., & Safra, S. (1997). A sub constant error probability low degree test, and a sub constant error probability PCP characterization of NP. In Proceedings of the 29th ACM symposium on theory of computing, El Paso (TX), USA (pp. 475–484). · Zbl 0963.68175 [26] Tien, J. M., & Kamiyama, A. (1982). On manpower scheduling algorithms. SIAM Review, 24(3), 275–287. · Zbl 0482.90040 · doi:10.1137/1024063 [27] Veinott, A. F., & Wagner, H. M. (1962). Optimal capacity scheduling: Parts I and II. Operation Research, 10, 518–547. · Zbl 0113.14301 · doi:10.1287/opre.10.4.518
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.