Combining integer programming and the randomization method to schedule employees.

*(English)*Zbl 1173.90406Summary: We describe a method to find low cost shift schedules with a time-varying service level that is always above a specified minimum. Most previous approaches used a two-step procedure: (1) determine staffing requirements and (2) find a minimum cost schedule that provides the required staffing in every period. Approximations in the first step sometimes cause the two-step approach to find infeasible or suboptimal solutions. Our method iterates between a schedule evaluator and a schedule generator. The schedule evaluator calculates transient service levels using the randomization method and identifies infeasible intervals, where the service level is lower than desired. The schedule generator solves a series of integer programs to produce improved schedules, by adding constraints for every infeasible interval, in an attempt to eliminate infeasibility without eliminating the optimal solution. We present computational results for several test problems and discuss factors that make our approach more likely to outperform previous approaches.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90B22 | Queues and service in operations research |

90C10 | Integer programming |

##### Keywords:

service operations management; employee scheduling; staffing requirements; nonstationary queues; randomization method; integer programming
PDF
BibTeX
XML
Cite

\textit{A. Ingolfsson} et al., Eur. J. Oper. Res. 202, No. 1, 153--163 (2010; Zbl 1173.90406)

Full Text:
DOI

##### References:

[1] | Atlason, J.; Epelman, M.A.; Henderson, S.G., Call center staffing with simulation and cutting plane methods, Annals of operations research, 127, 333-358, (2004) · Zbl 1116.90342 |

[2] | Atlason, J.; Epelman, M.A.; Henderson, S.G., Optimizing call center staffing using simulation and analytic center cutting plane methods, Management science, 54, 295-309, (2008) · Zbl 1232.90266 |

[3] | Aykin, T., Optimal shift scheduling with multiple break windows, Management science, 42, 591-602, (1996) · Zbl 0880.90065 |

[4] | Aykin, T.A., Composite branch and cut algorithm for optimal shift scheduling with multiple breaks and break windows, Journal of the operational research society, 49, 603-615, (1998) · Zbl 1131.90348 |

[5] | Bartholdi, J.J.; Orlin, J.B.; Ratliff, H.D., Cyclic scheduling via integer programs with circular ones, Operations research, 28, 1074-1085, (1980) · Zbl 0451.90075 |

[6] | Brusco, M.J.; Jacobs, L.W., A simulated annealing approach to the cyclic staff-scheduling problem, Naval research logistics, 40, 69-84, (1993) · Zbl 0769.90056 |

[7] | Buffa, E.S.; Cosgrove, M.J.; Luce, B.J., An integrated work shift scheduling system, Decision sciences, 7, 620-630, (1976) |

[8] | Cezik, T.; L’Ecuyer, P., Staffing multiskill call centers via linear programming and simulation, Management science, 54, 310-323, (2008) · Zbl 1232.90301 |

[9] | Dantzig, G.B., A comment on edie’s traffic delays at toll booths, Operations research, 2, 339-341, (1954) |

[10] | Edie, L.C., Traffic delays at toll booths, Operations research, 2, 107-138, (1954) |

[11] | Feldman, Z.; Mandelbaum, A.; Massey, W.A.; Whitt, W., Staffing of time-varying queues to achieve time-stable performance, Management science, 54, 324-338, (2008) · Zbl 1232.90275 |

[12] | Fukunaga, A.; Hamilton, E.; Fama, J.; Andre, D.; Matan, O.; Nourbakhsh, I., Staff scheduling for inbound call centers and customer contact centers, AI magazine, 23, 4, 30-40, (2002) |

[13] | Gans, N.; Koole, G.; Mandelbaum, A., Telephone call centers: tutorial, review, and research prospects, Manufacturing and service operations management, 5, 79-141, (2003) |

[14] | Grassmann, W.K., Transient solutions in Markovian queueing systems, Computers and operations research, 4, 47-53, (1977) |

[15] | Green, L.V.; Soares, J., Computing time-dependent waiting time probabilities in \(M(t) / M / s(t)\) queueing systems, Manufacturing and service operations management, 9, 54-61, (2007) |

[16] | Green, L.V.; Kolesar, P.J.; Soares, J., Improving the SIPP approach for staffing service systems that have cyclic demand, Operations research, 49, 549-564, (2001) · Zbl 1163.90423 |

[17] | Green, L.V.; Kolesar, P.J.; Soares, J., An improved heuristic for staffing telephone call centers with limited operating hours, Production and operations management, 12, 46-61, (2003) |

[18] | Green, L.V.; Kolesar, P.J.; Whitt, W., Coping with time-varying demand when setting staffing requirements for a service system, Production and operations management, 16, 13-39, (2007) |

[19] | Holmström, K., The TOMLAB optimization environment in Matlab, Advanced modeling and optimization, 1, 47-69, (1999) · Zbl 1115.90404 |

[20] | Ingolfsson, A., 2005. Modeling the \(M(t) / M / s(t)\) queue with an exhaustive discipline. Working paper. <http://www.business.ualberta.ca/aingolfsson/publications.htm>. |

[21] | Ingolfsson, A.; Haque, M.A.; Umnikov, A., Accounting for time-varying queueing effects in tour scheduling, European journal of operational research, 139, 585-597, (2002) · Zbl 0995.90030 |

[22] | Ingolfsson, A.; Akhmetshina, A.; Budge, S.; Li, Y.; Wu, X.A., Survey and experimental comparison of service level approximation methods for non-stationary \(M(t) / M / s(t)\) queueing systems, INFORMS journal on computing, 19, 201-214, (2007) · Zbl 1241.90034 |

[23] | Jackson, K., Thinking beyond the old 80/20 rule, Call center magazine, 15, January, 54-56, (2002) |

[24] | Jagers, A.A.; Van Doorn, E.A., Convexity of functions which are generalizations of the Erlang loss function and the Erlang delay function, SIAM review, 33, 281-282, (1991) |

[25] | Jennings, O.B.; Mandelbaum, A.; Massey, W.A.; Whitt, W., Server staffing to meet time-varying demand, Management science, 42, 1383-1394, (1996) · Zbl 0880.90052 |

[26] | Katz, K.L.; Larson, B.M.; Larson, R.C., Prescription for the waiting-in-line blues: entertain, enlighten, and engage, Sloan management review, 32, December, 44-53, (1991) |

[27] | Kolesar, P.J.; Rider, K.L.; Crabill, T.B.; Walker, W.E., A queuing-linear programming approach to scheduling police patrol cars, Operations research, 23, 1045-1062, (1975) · Zbl 0315.90033 |

[28] | Thompson, G.M., Accounting for the multi-period impact of service when determining employee requirements for labor scheduling, Journal of operations management, 11, 269-287, (1993) |

[29] | Thompson, G.M., Labor staffing and scheduling models for controlling service levels, Naval research logistics, 44, 719-740, (1997) · Zbl 0891.90093 |

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.