The assignment method of linear programming can be used for both loading and employee scheduling.

cheduling is an important step in planning the workload in any organization. Proper scheduling can help optimize many avenues of business from staff scheduling to fleet scheduling where there are many different combination of utilizing resources with different set of constraints. When done manually, this can prove to be a very time consuming and often might not lead to the most optimum solution and is not deterministic. This is where linear and integer programming, which are key techniques for discrete optimization problems, helps us in solving complex scheduling problems with a multiple set of constraints. By formulating the scheduling as a linear programming problem, we are able to determine the best possible outcome for many constraints such as number of resources, number of shifts, week-off for each resources, allocating resources based on budget or work load and so on. The program also becomes highly scalable when new constrains or new resources are added to the environment.

In this particular example, we formulate roster preparation as a linear programming problem. The preparation of a roster for a team is a time-consuming activity for the manager, when done manually, especially in teams with a large number of associates, where the manager has to give considerations to the preference of each employee. Further, the number of associates required to be present on a shift might vary depending on various factors like weekday vs weekend, the workload forecasted for the week. The automation of shift schedule with a minimum number of input parameters from the manager is an effective solution that will reduce the time taken by the manager for preparing the roster.

Linear programming is a mathematical modeling technique which uses optimization to give a best possible outcome to a set of input constraints. This is a very useful technique in quantitative decision making in business planning and is widely used in many practical applications. Different open source solvers that are available for linear programming such as SCIP, GLPK, or Google’s GLOP, and advancement in python programming framework to adapt writing constraints understandable by the solvers has led to many applications being solved as linear or integer programming. Schedule optimization is a class of problem that can be solved effectively with linear programming.

Problem statement

There are several constraints that must be handled for a proper roster. The roster is typically prepared in the last week of the month for the next 5 to 6 weeks in advance, and also takes into account preference of the associates like planned leave, shift preferences on certain days, week off, the maximum number of consecutive days that the employee is working, etc.

Currently, many teams follow the manual process of preparing the roster with an excel sheet, however, this results in violation of certain constraints and a lot of manual effort to come up with an acceptable roster for the entire team.

The automated shift scheduler will take into account various constraints and will present a roster for many weeks into the future, which can be reviewed and then modified only for a few specific scenarios.

The few constraints of the shift scheduler are:

1. There are two shifts (or three for certain teams) where each shift consists of 8 working hours, and there is a minimum number of resources that should be present in each of those shifts.
2. Each associate should have at most one shift per day.
3. Each associate should work only for 5 days each week and should have 2 days week off. Hence no associate should work more than 5 consecutive days during any period.
4. There should be a rotation of shift after alternate weeks or after every two weeks
5. Each associate should work on the same shift the next day and shift rotation between morning to evening (or vice versa) should happen only after a week off.
6. The associates of different levels should be split evenly across the different shifts.

Input for the program

The minimum input that is needed to execute the program is the resource list and their availability, number of shifts on each day, and number of slots to fill within each of the shifts. Additional information such as preferred shift for each of the employee on a particular day national holidays can be added to the program to handle specific cases. We have kept the mandatory inputs needed for the program to execute to a minimum so that the program can be reused across multiple teams.

Additionally, also as a future scope of improvement, we can look at the resource utilization from the last roster, we can see how much of the planned capacity is utilized and can further tune the program to optimize the resources needed for the current month.

Problem formulation

The problem formulation is the key step in the linear programming. The decision variables and the constraints have to be correctly declared to yield the desired optimum results. A linear programming problem consists of a set of decision variables, which is optimized for either a minimized or a maximized for the value that it finally takes in the optimum solution. Also, there are set of constraints, which has restrictions on what values the decision variables can take.

Notations

There are three binary decision variables for each employee and for each of the day (for two shifts). They are Mij for morning shift, Eij for evening shift, and Lij if the employee is on week off or on a leave. Only one of the three variables are set to 1 for an employee in a day, because they can either work in morning shift, or in evening shift or can be on week off.

Objective function:

The objective function that we are maximizing here is the level of the associate multiplied by the sum of the shift that they are working in. We have taken maximization for the objective function because constraints will ensure that the minimum week offs are given for the associates, and if any shift has more associates working after the fulfilment of the minimum number of employee for the shift, it is a favorable outcome.

Constraints:

1. Each employee should work at most one shift per day. For an employee j for a particular day i, then only either of the variables M, E and L should be equal to 1. Employee j on day i can only work in morning, evening or can be on week off.

2. Each day and each shift should satisfy minimum resource constraint. The minimum resource constraint is obtained as the input to the program and for each day we make sure the shift is loaded with associates more than the minimum required for the shift.

3. Each employee should work the same shift the next day, but can rotate after a week off. This constraints take care of assigning continuous shift to the employee. For example we cannot assign morning shift to an employee on Tuesday if he had worked Evening shift on the previous day. But the rotation of shift is allowed after there is a week off for the associate.

4. Rotating shifts at least once in two weeks. We will have to rotate the associates between morning and evening shift at least once in every two weeks. Without this constraint, the program continued to assign employees to the same shift across all the days of the month in which they were working.

5. Each employee should not work more than 5 working days continually.

6. There should be two consecutive week offs. This is by far the most tricky constrain to write. For the binary variable L, the pattern to avoid on the three consecutive days is only 0–1–0 to ensure that the associate gets two consecutive days off.

We used PuLP package within python to solve this optimization problem. For 10 associates and 35 days (5 weeks) we had totally combination of 1775 constraints and 3 shifts x 10 employees x 35 days = 1,050 decision variables. Pulp was able to solve the optimization problem within 2 minutes to an optimum solution.

We also built a R-Shiny app on top of this python optimization, so that the users can input their input constraints and will be automatically generate the output for their team each month.

The key objective of the automatic shift roster generation is to considerably reduced the manual effort. Even though there are some minor changes that the team might need to do on case to case basis manually, this program gives a skeleton of roster on which those minimum changes can be made, instead of preparing the schedule from scratch each time.

Acknowledgments: This is a collaborative effort between Sreeraman Krishnan, and many other team who gave us valuable inputs to shape this tool.

References