Example of a scheduling problem
1. Example of a scheduling problem
In this lesson we will look at a scheduling problem which will cause us to reevaluate the way we define our decision variables.2. Scheduling problem
Imagine we are hiring truck drivers. The table shows the number of estimated drivers needed each day. The question we want to answer is, how many drivers in total do you need to hire. In this problem each driver works for 5 consecutive days, followed by 2 days off. In the US, the number of hours a driver is allowed to drive is highly regulated. Drivers are mandated to rest to eliminate the type of drowsiness that can lead to crashes. If we attempt to model this problem as a LP or IP problem how do we define the decision variables?3. Choosing decision variables
We could define the decision variable as the number of drivers that work on each day. However, this presents a number of problems. First, in our objective function we count the same driver multiple times if they work multiple days. For example, if a driver works on Monday and Tuesday the objective function is counting the same driver in the count of drivers who work on Monday and the count of drivers who work on Tuesday. This does not help us answer how many drivers do we need to hire. Also, we cannot model the constraint that a driver work 5 consecutive days with two days off. It is not uncommon to begin to modeling a problem and realize that you may need to adjust your decision variables.4. Choosing decision variables
What happens if we define the decision variable as the number of drivers beginning to work on day i. For example, X sub 0 is the number of workers who start their 5 consecutive working days on Monday and take Saturday and Sunday off. X sub 1 is the number of workers who start on Tuesday and have Sunday and Monday off. With the decision variables in this form our objective function avoids counting the same person multiple times. In addition, our constraint regarding time off is taken care of by how we defined the decision variables. With the decision variables in this form we ensure that a minimum of 11 truckers work on Monday by summing those who start on Monday, and those who start on Thursday through Sunday. We skip those who start on Tuesday and Wednesday because after their 5 working days they have Monday off. This same pattern follows through the remainder of the days. While this particular problem focused on scheduling truckers it can be applied in other contexts such as scheduling equipment mandatory downtime for preventative maintenance. An important take away from this example is that sometimes we must choose our decision variables to incorporate some of the constraints of the problem. On occasions, cleverness is needed to correctly define the decision variables.5. Coding example
Modeling this problem in PuLP might look something like this. We initialize the model with LpMinimize and define a list of numbers 0-through-6. This list is used with LpVariable-dot-dicts to create our variables. We use lpSum with list comprehension for the objective. Finally, we define our minimum constraints for each day of the week and solve the model.6. Summary
In summary, in this scheduling problem our initially designed variables did not work. Modeling is often an iterative process. When redefining the decision variables we incorporated some of the constraints in how we defined them. This type of scheduling problem is an example of the creative thinking that might be needed when modeling.7. Practice time!
Your turn to try out what we covered!Create Your Free Account
or
By continuing, you accept our Terms of Use, our Privacy Policy and that your data is stored in the USA.