Optimization Online


Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service System Staffing and Scheduling with Arrival Rate Uncertainty

Merve Bodur (mbodur***at***wisc.edu)
James Luedtke (jrluedt1***at***wisc.edu)

Abstract: We study server scheduling in multiclass service systems under stochastic uncertainty in the customer arrival volumes. Common practice in such systems is to first identify staffing levels, and then determine schedules for the servers that cover these targets. We propose a new stochastic integer programming model that integrates these two decisions, which can yield lower scheduling costs by exploiting the presence of alternative server configurations that yield similar quality-of-service. We find that a branch-and-cut algorithm based on Benders decomposition may fail due to the weakness of the relaxation bound. We propose a novel application of mixed-integer rounding to improve the Benders cuts used in this algorithm, a technique that is applicable to any stochastic integer program with integer first-stage decision variables. Numerical examples illustrate the computational efficiency of the proposed approach and the potential benefit of solving the integrated model compared to considering the staffing and scheduling problems separately.

Keywords: Stochastic programming, integer programming, staffing, scheduling, mixed-integer rounding

Category 1: Applications -- OR and Management Sciences

Category 2: Stochastic Programming

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: University of Wisconsin-Madison, November 11, 2014

Download: [PDF]

Entry Submitted: 10/14/2013
Entry Accepted: 10/14/2013
Entry Last Modified: 11/13/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society