A client of mine showed some interest in developing some MIP based workforce planning models. Column generation has been used successfully in such applications. To show how such an approach could look like, I have added a small example here: http://www.amsterdamoptimization.com/pdf/colgen.pdf.
The master problem is simply:
I.e. make sure you have enough shifts to handle all forecasted calls. Inside the algorithm we use a relaxed version of this.
The subproblems are a little bit more complicated: they form allowed shifts, and deal with minimum and maximum work time requirements and the introduction of appropriate breaks in a shift. A complete description of the conditions is:
- A day shift cannot exceed 9 hours, but is not allowed to be shorter than 4 hours.
- If a shift exceeds 8 hours, 0.75 break time is required of which 0.5 hour contiguous. If a shift exceeds 5.5 hours, a single break of 0.5 hours or two breaks of 0.25 hours is required. For shorter shifts a single break of 0.25 hours applies.
- Maximum contiguous time an operator can work without a break is 3.25 hours.
However as the subproblem only needs to form a single candidate shift, the subproblem is a very small MIP and solves fast. As a result the above schedule only takes 18 seconds to generate.
The complete model can look like:
If speed is everything, often a more brute force can be employed for these type of models: generate all possible shifts and solve just that single set covering problem. Even if done relatively unintelligently with pieces of code like:
| for k1 := 1 to 13 do |
for k2 := 1 to 13 do
for k3 := 1 to 13 do begin
k := k1+k2+k3;
if (k>=33) and (k<=36) then
the generation part goes very fast. Especially after stepping through the code with a debugger, it is always surprising how fast such code executes. For this problem we only needed to generate 20579 shifts (using my interpretation of the conditions – slightly more strict than the referenced paper). Also the resulting master problem solves very fast. An additional advantage is that this approach provides proven global optimal solutions. In this case we saw that the column generation heuristic gave the same objective as the complete enumeration model.