An efficient two-phase algorithm for cyclic days-off scheduling

An efficient two-phase algorithm is presented for solving the cyclic manpower days-off scheduling problem with two consecutive off days per week. First, a simple formula is used to calculate the minimum workforce size. Next, this minimum is incorporated as a constraint in a continuous linear programming (LP) model of the problem, ensuring an optimum integer solution. The new algorithm can handle the case in which the costs of different days-off patterns are not equal. Computational experience with 1250 test problems shows this algorithm to be significantly more efficient than other available solution methods.