Bechtold-Jacobs generalized model for shift scheduling with extraordinary overlap

In constructing working shifts, the classical Dantzig (Operation Research 2:339–341, 1954) set covering model uses a great number of variables which makes computation very complicated for some cases that incorporate a high degree of break-placement flexibility. Bechtold and Jacobs (Management Science 36:1339–1351, 1990) proposed an implicit model under the assumption that there is no extraordinary overlap, which considerably reduced the number of variables. In this paper we give a generalization that is valid without this hypothesis by adding a minimal set of constraints. Also, in some cases where there is extraordinary overlap we reduce our constraint set to a subset with the same number or less than that of Bechtold and Jacobs. I. Addou’s current address is Département de Mathématiques et Statistique, Université de Montréal, Succ. Centre-ville, Montréal, Québec, Canada, H3C2J7; e-mail: addou@dms.umontreal.ca.