Solving the shift and break design problem using integer linear programming

In this paper we propose a two-phase approach to solve the shift and break design problem using integer linear programming. In the first phase we create the shifts, while heuristically taking the breaks into account. In the second phase we assign breaks to each occurrence of any shift, one by one, repeating this until no improvement is found. On a set of benchmark instances, composed by both randomly-generated and real-life ones, this approach obtains better results than the current best known method for shift and break design problem.

Automated summary

This paper introduces a two-phase approach using integer linear programming to solve the shift and break design problem. The approach creates shifts while considering breaks heuristically in the first phase, and assigns breaks to shifts in the second phase until no improvement is found. Results show that this approach outperforms the current best known method for shift and break design problem on a set of benchmark instances.