View article

The requirements in an MSD problem are given for h days, which usually span a small multiple of a week, and are valid for a certain amount of time ranging from a week up to a year. Each day j is split into n equal-size smaller intervals [ti, ti+ 1), called timeslots, which can last from a few minutes up to several hours. The staffing requirement for the ith timeslot (identified by its starting time ti, i= 0,..., n− 1), on day j∈{0,..., h− 1} is fixed. For every i and j we are given an integer value bi, j representing the number of persons needed at work from time ti until time ti+ 1 on day j, with cyclic repetions after h days.

An example of workforce requirements with h= 7 is shown on the left side of Table 1, the first day being labeled ‘Mon’etc. In the table, for conciseness, timeslots with same requirements are grouped together (the example is adapted from a real call-center). When designing shifts, not all starting times are feasible, nor are all lengths allowed. For this reason, the input also includes a collection of shift types, each of them characterized by a minimum and maximum starting time, a mimimum and maximum length, and time granularity equal to the length of the timeslots. The right side of Table 1 shows an example of a set of shift types. Each shift Is, l with starting time ts (s∈{0,..., n− 1}) and length l, belongs to a type, ie, its length and starting times must necessarily lie inside the intervals defined by one type. In the following, the type of shift I is denoted by T (I).