A shift with a valid break allocation is called a duty. Each template shift has as many shifts as days in the planning horizon.ĭuty A shift itself is not yet complete: it usually needs breaks. Shift A template shift combined with a day in the planning horizon constitutes a shift. Each template shift s must derive from a shift type t, meaning that the starting time of s should lie at or between the earliest and latest starting times of t, and the duration of s should be at or between the minimum and maximum durations of t. Template shift A template shift specifies a starting time and a duration.
Figure 1 gives an example, where the shift types are Morning, Day, Evening and Night shifts. Shift type A shift type specifies an earliest starting time, a latest starting time, a minimum duration and a maximum duration. To explain duties, we need the notions of shift type, template shift, and shift. Per time period we have to design duties that fulfill the staffing requirement. For each time period t the staffing requirement \(R_t\) is given. The planning horizon is divided into time periods of a constant duration, such as 5 min. The problem is cyclic, meaning that a night shift on the last day will continue on the first time periods of the planning horizon. The planning horizon consists of a set of consecutive days such as a week. We use the same problem formulation as Di Gaspero et al. Section 3 gives an overview of related literature, Sect. Section 2 gives the problem description in more detail. The structure of this article is as follows. Having said that, it should be noted that obtaining a (proven) optimal solution for a shift and break design problem of moderate size, is still out of reach for general purpose exact solvers. Our paper shows that this approach is indeed feasible, given the “right” decomposition of the problem. The main idea of this paper is to try to exploit the power of contemporary ILP solvers. ( 2010) that combined local search with constraint programming techniques. The resulting algorithm seems to outperform the previously best performing method suggested by Di Gaspero et al. The main contribution of this paper is to show that the shift and break design problem can be solved by contemporary standard ILP solvers when decomposed into two, combinatorially defined aggregation levels. Eventually, understaffing, overstaffing and the number of template shifts will translate into penalty costs. This can be important, because schedules with a small number of different template shifts are easier from a managerial perspective, and better for personnel acceptance. Next to avoiding under- and overstaffing, an important goal in the shift design problem is to select a small number of template shifts. It is assumed that under- and overstaffing is possible, yet undesirable. During a break, duties are not counted as contributing to the fulfillment of the staffing requirements, and in addition, also not during the time period immediately after a break. A duty can then be assigned to a person, and the work periods in the duty contribute to fulfill the given staffing requirements. On a given day, one or more duties, usually with different break allocations, can be created for a shift. The breaks in a duty are restricted by a large number of conditions which we will discuss in more detail in the next section. A shift usually requires breaks to be admissible when an admissible set of breaks is assigned to a shift, we will call a duty. A shift is thus specified by a day, starting time, and a duration. A selected template shift can then be used on different days, leading to shifts. A template shift is characterized by a fixed starting time and a fixed duration, such as 09:00 and 8 h, while a shift type only prescribes the intervals for possible starting times and durations. In this problem a set of template shifts has to be selected from a set of possible shift types. In this paper we consider the shift and break design problem which in this specific form was introduced by Di Gaspero et al. The interest can be explained by labor cost being a major direct cost component for companies. After its introduction it has received a great deal of attention in the literature and has been applied to numerous areas such as airlines, health care systems, police, call centers and retail stores (Ernst et al. Personnel scheduling was first introduced by Edie ( 1954) and formulated as a set covering problem by Dantzig ( 1954) in the 1950s.