By: Sweta S and Gireesh Sundaram, Walmart Global Tech

 

Scheduling 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 combinations of utilizing resources with different sets of constraints. When done manually, this can prove to be 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 multiple sets of constraints. Linear programming is a mathematical modeling technique which uses optimization to give a best possible outcome to a set of input constraints. Different open source solvers that are available for linear programmings 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. The program also becomes highly scalable when new constraints or new resources are added to the environment. In this particular example, we formulate roster preparation as a linear programming problem. By formulating the scheduling as a linear programming problem, we are able to determine the best possible outcome for many constraints such as the number of resources, the number of shifts, week-off for each resources, allocating resources based on budget or workload and so on. 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 to prepare the roster.

Several constraints 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 preferences 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 problem is formulated as a linear programming problem. A typical 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 is a set of constraints, which has restrictions on what values the decision variables can take. 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. 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 fulfillment of the minimum number of employee for the shift, it is a favorable outcome. We have considered the following 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 constrain. The minimum resource constrain 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 constrains 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 constrain, the program continued to assign employees to the same shift across all the days of the month in which they were working; Each employee should not work more than 5 working days continually; 5)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 constrains 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 reduce manual effort. Even though there are some minor changes that the team might need to do on a case by case basis, this program provides a skeleton of roster on which those changes can be made easily, there by saving time and ensuring optimized schedule

 

References:

1. Scheduling IT Staff at a Bank: A Mathematical Programming Approach

2. Optimized shift work