The Employee Scheduling Problem using EXCEL
The Excel File – Scheduling.xlsm
Create a schedule that covers the required number of employees at all times each day of the week and be as fair as possible to all employees in scheduling.
The Parking Department at the University has about 40-part time student workers, and everyone has a specific number of hours they would like to or are allowed to work every week. We want to keep the difference between allocated number of hours and desired number of hours as low as possible, and as fair as possible for all. Each employee is also a college student, and thus will have a different schedule of availability. The department regulation does not allow employees to be scheduled for consecutive shifts.
Apart from the class schedule employees need to have the option of taking time offs on a weekly basis. Each week the requirement of number of employees required per shift is different than the last, thus a new schedule must be created each week.
Within each day there will be so many employees required for particular shifts (ex: 3 employees from 9am-12pm, 4 from 12am-3pm, and 4 from 3pm-6pm). The slots are defined and remain the same every week. Therefore a schedule must be created from a blank slate provided only with…
- The employees and their information (# of desired hours, availability)
- number of employees required to be on duty at a give time slot (shift).
I was looking for a method that was easy to use and one that would not require any additional purchases. Doing it in Excel was the logical step. The shift times were fixed ( 3 hour shifts starting at 9 A.M. , 12P.M. , 3 P.M. and 6 P.M.). I decided to model it like the assignment problem.
Assignment problem is one of the special cases of transportation problems. The goal of the assignment problem is to minimize the cost or time of completing a number of jobs by a number of persons. An important characteristic of the assignment problem is the number of sources is equal to the number of destinations. ( A tutorial on using the solver and the assignment problem can be found here )
Solving it in Excel !
The Excel File – Scheduling.xlsm
The Solver add in in excel can be used for dealing with these problems. However Excel limits the number of variables to 500 which is way lesser than what the model would require! I decided to use the Open Solver .The open solver works the same way your excel solver works! It does take in the constraints that you add to the excel solver. The final output is binary. The 1 = Allocated Shift and 0 = No Allocation.
The model consists of two matrices. One where allocation is done by changing 0’s and 1’s and the other matrix consists of a class schedule. The shifts during which student workers have class are marked with 1000 ( Arbitrary high value) and the shifts in which they are available to work are marked with 8 ( Arbitrary low value). The allocation is done such that the objective is to minimize the value ( Sum Product of the two matrices) . For the image shown above the value in the objective cell will be calculated using the formula =SUMPRODUCT(C3:Z42,C50:Z89)
Once the matrices are set up we need to add the constraints to the model. Inserting values of 1000 act as soft constraints. We need to make provision to include two major things in the hard constraint.
- The number of Employees required per day per shift ( Ex. 3 Employees on Monday for the 9 – 12 Shift)
- The maximum number of shifts that employees can work or want to work in a week.
To ensure fairness in the shift allocation and the Department regulation add a few other constraints as well.
- Minimize difference between available hours and allocated hours.
- Ensure employees are not allocated consecutive shifts.
The constraints can be added by clicking on Data –> Solver Addin (Instruction on adding and accessing the Solver Add in ) . When the constraints are added it should look something like this.
The first constraint seen in the “Subject to Constraints” box above is the binary constraint. You will notice that the cell range is the same in the “By Changing Variable cells” box.
The values in the column AC are the sum of the number of shifts allocated in a week. The values in cells AB are the maximum number of shifts that employees can be allocated. It is similar for values in columns AE and AF except that they consider the total number of hours ( where the hours are calculated by Duration of shift * Number of shifts. The constraint here will be Shifts allocated < = Availaible
For column AH a weighted sum of all shifts is calculated and a minimum value is set on the top most cell in the column. This is done to ensure minimum difference between avaialible and allocated shifts and to ensure fair allocation.
For Columns AJ to AN the cells show a total number of shifts allocated in a day and a maximum value can be set. (setting it at 1 ensures no consecutive allocation is done since only one shift is allocated in a day)
Another constraint that we need to add is that of requirement per shift. the constraint here will be that Assigned = Requirement. The Assigned row in the image below is the sum of all allocations done for a particular shift on a particular day.
Once the constraints are added we will have to run it through the Open Solver. ( Excel solver has a variable limit and will work only for models containing upto 500 Variables ).
Click on the solve button of the open solver ( Read the Open Solver . documentation to run the solver) The output generated should look something like this. If for example Jefferson is allocated a shift on Monday 12P.M. to 3P.M That cell will show a 1 . Jackson has no shift allocated on Monday from 9A.M. to 12P.M. so the cell shows a zero.
In some cases it can happen that a soft constraint is violated ( A shift is allocated to a person during his class schedule). The fastest way to recognize this is that the Objective Value is significantly high. We can use different methods to recognize and get past this issue.
The next logical step is to create a schedule which is in an easy to understand format , a human can override to make adjustments etc. for this part we will have to make use of VBA.
A dashboard was created for ease of use.
Options of editing class schedule and saving the schedule as PDF were added too.
I will add a detailed section about the VBA part sometime in the future. Till then Happy Scheduling!
The Excel File – Scheduling.xlsm