Bounded flexibility in days‐on and days‐off scheduling

This article presents a flexible days‐on and days‐off scheduling problem and develops an exact branch and price (B&P) algorithm to find solutions. The main objective is to minimize the size of the total workforce required to cover time‐varying demand over a planning horizon that may extend up to 12 weeks. A new aspect of the problem is the general restriction that the number of consecutive days on and the number of consecutive days off must each fall within a predefined range. Moreover, the total assignment of working days in the planning horizon cannot exceed some maximum value. In the B&P framework, the master problem is stated as a set covering‐type problem whose columns are generated iteratively by solving one of three different subproblems. The first is an implicit model, the second is a resource constrained shortest path problem, and the third is a dynamic program. Computational experiments using both real‐word and randomly generated data show that workforce reductions up to 66% are possible with highly flexible days‐on and days‐off patterns. When evaluating the performance of the three subproblems, it was found that each yielded equivalent solutions but the dynamic program proved to be significantly more efficient. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 678–701, 2013