Network-Based Mathematical Programming Approach to Optimal Rostering of Continuous Heterogeneous Workforces

摘要

We present a linear programming (LP) approach to a generalized personnel tour scheduling integer programming (IP) problem based upon a minimum cost network-flow formulation with specialized side constraints. The formulation simultaneously incorporates many realistic constraint types and optimally solves the IP tour scheduling problem for industries with continuous (24 hour) operations and a heterogeneous workforce with varying availabilities, shift preferences, restrictions on working consecutive shifts, differing skill- sets, and minimum and maximum shift requirements per week. Our work is the first to solve this generalized class of IP problems optimally. Problems of this complexity routinely occur in industry but are computationally prohibitive to solve. Integer solutions to our tour scheduling problem are found without branching, bounding, or cutting schemes. This allows the CPLEX interior-point method to generate solutions orders of magnitude faster than the corresponding integer program does. Our methodology is demonstrated by finding an optimal tour schedule for staffing the four main Computer Commons at Arizona State University, a problem of order 10,000 binary variables and 1,000 constraints in 0.12 CPU seconds. It is also used to perform the calculations for a generalized staff sizing problem.