 ## Scheduling with ease: Cost optimization tutorial for Python | |
[ 所属分类 开发（python） | 发布者 店小二04 | 时间 2018 | 作者 红领巾 ] 0人收藏点击收藏
Scheduling with ease: Cost optimization tutorial forpython Learn how to quickly solve optimization problems with linear programming inPython Introduction Context

Congratulations! You’re the proud new owner of the coolest store in town. To keep the operation running, you need to ensure that you have the correct number of workers scheduled for each shift. In this tutorial, we’ll design the lowest cost schedule for the upcoming week.

Considerations

For the coming week, each day has two shifts of 8 hours. You currently have ten employees, four of which are considered managers. For any shifts beyond 40 hours in a given week (5 total shifts), you pay your employees overtime. To be fair to your employees, you decide that everyone has to work at least 3 shifts, but no more than 7 shifts. And to ensure that the shop runs smoothly, each shift requires at least one manager. Structuring theproblem

Before diving into the code, let’s add structure to our task by defining our objective, variables, and constraints.

Objective function

In simple words, we want to design the lowest cost schedule, accounting for both regular time and overtime. We can define this mathematically as: Where w is our list of workers, RegCost and OTCost are the dollar costs of a regular and overtime shift for each worker, respectively, and RegShifts and OTShifts are the total number of regular and overtime shifts for each worker, respectively.

Variables We will create a list of variables for every worker/shift combination (e.g. [‘Employee1’,‘Monday1'], [‘Employee2’,‘Monday1’], etc.). Each of these variables will be a binary value to signify if a worker is scheduled (1) or not (0). We’ll also need to deal with the split of regular time and overtime, which we’ll handle as a hybrid of variable and constraint. Constraints

From the problem statement above, we know that there are a number of special considerations that we need to follow. To make sure that our optimized schedule is acceptable, we’ll create specific constraints:

Total number of workers staffed equals total number of workers required for each shift Workers must stay between global minimum and maximum number of shifts Workers can only be scheduled when they are available (handled in decision variable ‘x’) At least one manager staffed per shift Creating our model inPython Preparing thedata

Before diving into the the optimization model, we need some (illustrative) data to work with. Since loading data into Python is out of the scope of this tutorial, we’ll move through this part quickly.

Here’s a recap of what we now have:

A list of our 14 shifts (two shifts per day for one week) and our 10 employees (lines 7 9) The number of workers needed for each shift (lines 12 13) The availability of each worker for each shift (lines 17 23) A list of who are managers and a list of who are not managers (lines 26 27) The cost of a shift for each worker, both regular and overtime (lines 31 36) A few global assumptions for min and max shifts and how many shifts are allowed before triggering overtime (lines 40 43) Initialize themodel

Note: As can be seen in the above code, we are using a package called Gurobi . Gurobi is an optimization solver that is available for a number of programming languages. While the full version of Gurobi requires a commercial license, you can get an academic or online course license to run a limited version for free.

We first need to create the shell of our model. We do this with the following code:

model = Model(“Workers Scheduling”) Add decision variables

Let’s turn our structured variables into code:

First, we need to create binary variables for each worker/shift combination. We can do this with Gurobi’s addVars function ( Note: if only adding one variable, use addVar instead ). We specify that the variable is binary and we also read in the avail dictionary that we created before as a ub (“upper bound”). Each Gurobi variable has an upper and lower bound. Since we are using binary variables, naturally our variables must equal 0 or 1. By setting the upper bound equal to the values in avail , we are able to embed the constraint that certain worker/shift combinations must equal 0 (i.e. when that worker is unavailable).

Next, we have to create variables to handle the regular and overtime hours. As was mentioned before, we’ll handle this split as a combination of variable and constraint. For now, we simply create the variables for each worker without further specification. The one exception is that we set overtimeTrigger to be a binary variable (0 when there is no overtime for a given worker this week and 1 when there is overtime).

Similarly, let’s turn each constraint outlined above into code, using the addConstrs (adding multiple constraints at a time) and addConstr (adding one constraint at a time) functions.

First, we specify that the sum of assigned workers (1 for each scheduled worker, 0 for each non-scheduled worker) for each shift equals the total shift requirement:

Next, we deal with the split between regular time and overtime. To capture this correctly, we take a conservative approach. First, we specify that the number of regular shifts plus the number of overtime shifts is equal to the total number of shifts for each worker. Then, we ensure that the number of regular shifts is less than or equal to the number of shifts specified as our overtime trigger. We do this to ensure that regular shifts are accounted for before overtime shifts. To double down on this, we add the final constraint that says that if the number of regular shifts for a worker is less than 5 ( OTTrigger ), then the binary trigger for overtime is set to 0.

With this in place, we can finish our final constraints. Similar to above, we calculate the total number of assigned shifts for each worker. We specify that this must be greater than or equal to the global input for minimum number of shifts and less than or equal to the global maximum number of shifts. Finally, we handle the requirement for each shift needs at least one manager to be staffed.

Define the objective function

Our objective is to minimize the total cost of the workers scheduled. We can handle this quite simply by defining a cost function that sums the total number of regular shifts times the cost of a regular shift for each worker and the total number of overtime shifts times the cost of an overtime shift for each worker. We tell Gurobi that the goal is to minimize this using ModelSense . Finally, we use setObjective to specify that Cost is the objective function.

Running the optimization

Before running the optimization, it can be helpful to inspect the model. A great way to do this is:

With this code, you’ll be able to see the objective function, variables, constraints, etc. listed as formulas, which can be particularly helpful to ensure t

1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责；
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。 技术大类 | 开发（python） | 评论(0) | 阅读(90)