27 March 2023
A common application of optimization modelling is the scheduling of staff to meet demand. Scheduling problems can be difficult to solve, as there are often very specific requirements that need to be met, including staff availability, working hours, break times, etc.
One approach for formulating scheduling problems is to enumerate all possible shift patterns and then decide how many of each shift pattern to use so that we meet the various constraints at least cost.
Enumeration of all possible shift patterns is often not as difficult as it may sound. We used a similar technique in the model Green manufacturing via cutting patterns. In that situation, there were potentially thousands of possible patterns, requiring an automated process to generate them all. In the staff scheduling situation there is usually a much smaller number of possible patterns, so manual enumeration is often possible.
This article implements a staff scheduling model in Excel and solves it using the CBC solver via OpenSolver. The next article implements the same model in Python, solves it using the CBC solver via Pyomo, then compares the Excel and Python model versions.
Download the models
The model is available on GitHub.
Situation
Our business opens at 6:00am and closes at 6:00pm. We need to create a shift schedule for our staff to meet the demand, expressed as the minimum number of staff required in each half hour. Demand is low at the start of the working day, rises to a peak at around noon, then declines towards the end of the working day. Our objective is to minimize the total wage cost for the day.
We have three categories of staff. Each category may be assigned to shifts that start at the beginning of any half-hour, provided that:
- Full-time staff work 8 hours per day, plus a 1 hour unpaid break in the middle of their shift. Up to 7 of these staff are available, at a wage of $22.00/hour each.
- Some part-time staff work 6 hours per day, plus a 0.5 hour unpaid break in the middle of their shift. Up to 6 of these staff are available, at a wage of $21.00/hour each.
- Some part-time staff work 4 hours per day, with no unpaid break. Up to 14 of these staff are available, at a wage of $20.00/hour each.
Model 1
Model 1: Design
Enumerate possible shift patterns
The central idea of this model is to enumerate all possible shift patterns and then decide how many people will work each shift.
For a full-time person, there are only seven possible shift patterns within our working hours. That is:
- The first possible shift pattern starts with the half-hour beginning at 6:00am, ends at the half-hour beginning 2:30pm, with a one hour break in the half-hours beginning 10:00am and 10:30am.
- The next possible shift pattern starts with the half-hour beginning at 6:30am, ends at the half-hour beginning 3:00pm, with a one hour break in the half-hours beginning 10:30am and 11:00am.
- Similarly in half-hour increments.
- The last possible shift pattern starts with the half-hour beginning at 9:00am, ends at the half-hour beginning 5:30pm, with a one hour break in the half-hours beginning 1:00pm and 1:30pm.
These seven shift patterns, plus those for the 6h and 4h categories, give a total of 36 shift patterns, as shown in Figure 1. Each row is a shift, and each square represents a half-hour slot.
If we have other shift patterns, then it would be easy to extend the data to include them. For example, we could have a split shift, where people work for four hours in the morning (the half-hours beginning 6:00am to 9:30am), and four hours in the afternoon (the half-hours beginning 2:00pm to 5:30pm), with a four hour gap between. Such a split shift would be more useful if our demand has morning and afternoon peaks.
Model 1: Implementation
The key to our formulation is that we need to decide how many of each possible shift pattern to use. Therefore, we have an integer variable for the usage of each shift pattern and then calculate how many people are working in each half-hour by multiplying the usage variable by the shift pattern data from Figure 1. An example result, for the full-time shift patterns, is shown in Figure 2.
That is, we've allocated two staff to the pattern that begins at 6:00am, one staff to the pattern that begins at 7:00am, and two staff to the pattern that begins at 7:30am. These staff contribute towards meeting the demand for the number of staff in each half-hour of the working day. We continue this process for the other shift patterns, to get our total staffing for each half-hour of the day. We then need a constraint that ensures that the staff allocation in each half-hour is at least the specified demand in that half-hour.
In addition, we need to sum over each category of staff to ensure that we're using no more people than are available. We have seven full-time staff available, so it is feasible to use five of them.
Finally, we can calculate the staffing cost by multiplying the usage of staff in each category by their respective hourly rates (adjusted by the half-hour length of each time slot).
Model 1: Solver model
Objective function
The Solver model is shown in Figure 3. Our objective is to minimize fCostTotal, as specified above.
Variables
The model has one set of variables:
vAllocation. The integer number of staff allocated to each shift pattern.
Constraints
The constraints are:
fStaffUsed <= dAvailable. We use no more than the number of people available in each category.fStaffAllocated >= dPeopleRequired. The number of allocated staff at least meets the demand for staff in each half-hour.
Solution method
Our model is small enough that either Solver or OpenSolver can be used. However, we use OpenSolver so that we can use the CBC solver, like we will in the subsequent Pyomo version of this model.
Model 1: Analysis
Optimal solution
Figure 4 shows the optimal solution's number of staff allocated to meet demand in each half-hour of the day. Note that there are many alternative optima. The dark bars show the demand, while the light bars indicate where we have more people allocated than are needed. The optimal objective function value is $2,324 staff cost for the day.
The solution's allocation matches demand very well, with only a few half-hours having more people than we need. This surplus is a consequence of fitting fixed shift patterns to a varying demand profile. But in the half-hour beginning 11:30am we have three surplus people, which is more than we want.
Figure 5 shows the allocation of staff from each category. Most of the staff are from the part-time 4 hour per day category. This isn't surprising, as that category has the lowest wage rate, so the model will prefer using them rather than the more expensive categories. However, we want to have more of our available full-time staff allocated to the day. Only three of the available seven full-time staff have been scheduled – but we want at least five full-time staff scheduled. In addition, we want at least one full-time person to be there at opening time (which this solution has), and at least two full-time people there at closing time (which this solution does not have).
Model 1 extended
Model 1 extended: Design
The model performs as expected. But after examining the solution above, it emerges that we have some additional requirements. This type of model evolution is typical.
That is, we want to extend the model to add three features:
- Limit the maximum surplus in a half-hour.
- Require a minimum number of people from each category (specifically full-time people) scheduled during the day.
- Require that some specific shifts be used with a minimum number of people.
Model 1 extended: Implementation
We need to extend the model by adding constraints to implement the three new features. We do this by adding assumptions for each of the new features, as shown in the spreadsheet, then adding new constraints as shown below.
Model 1 extended: Solver model
Objective function
The extended Solver model is shown in Figure 6. Our objective is unchanged.
Variables
The variables are unchanged:
vAllocation. The integer number of staff allocated to each shift pattern.
Constraints
We retain the original two constraints and add three more, giving:
fStaffUsed <= dAvailable. We use no more than the number of people available in each category.fStaffAllocated >= dPeopleRequired. The number of allocated staff at least meets the demand for staff in each half-hour.fStaffAllocated >= dPeopleMin. The minimum number of people from each category for the day.fSurplusPeople <= dSurplusMax. The maximum number of surplus people in each half-hour.vAllocation >= dShiftRequired. The minimum number of staff allocated to each shift pattern. Most of these values should be zero.
To achieve the desired schedule, we set the maximum surplus to one person per half-hour. Note that setting the maximum surplus to zero makes the model infeasible, so a maximum of one is the best we can do with this data. We also require the full-time shift beginning at 6:00am to have one person, and the full-time shift beginning at 9:00am (through to the half-hour beginning 5:30pm) to have two people. Finally, we require a total of at least five full-time staff be used during the day.
Model 1 extended: Analysis
Optimal solution
The extended model's optimal solution is shown in Figure 7. The optimal objective function value is $2,356 staff cost for the day – only $32 more than the original model, which is a small price to pay for our additional requirements. In this solution, the maximum surplus in a half-hour is one person, as required. Note that the total surplus (7 people half-hours) is the same as for the original model.
Looking at Figure 8, we see that our other new constraints have had the desired effect. That is, we now have one full-time (8h) staff scheduled for opening time and two full-time staff scheduled at closing time. We also have more, specifically five, full-time staff working during the day. This is a better schedule, so we're happy with this solution.
Conclusion
In this article we built a staff scheduling model in Excel. Scheduling problems can be difficult to formulate and solve. The model uses a technique of enumerated shifts to formulate the situation, which simplifies the formulation and enables efficient solution by the solver.
In the next article we replicate this model in Python using the Pyomo library.
If you would like to know more about this model, or you want help with your own models, then please contact us.