Skip to content

Instantly share code, notes, and snippets.

@adikamath
Last active November 2, 2018 04:50
Show Gist options
  • Save adikamath/72812b2cc1d31a9d3670ded9a723d121 to your computer and use it in GitHub Desktop.
Save adikamath/72812b2cc1d31a9d3670ded9a723d121 to your computer and use it in GitHub Desktop.
Display the source blob
Display the rendered blob
Raw
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h2>Introduction</h2>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The problem I'm trying to solve is this- there are multiple batches of products that need to be produced in a week and that share the same manufacturing cell. The manufacturing cell is open from Monday until Friday and runs two shifts per day which consists of a regular shift of 7.5 hours and an overtime shift of upto 5 hours. There are 6 operators working in the cell and each can work on one unit independently. We have to ensure that the production is scheduled such that the total cost of production is minimized for the week."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h2>Model Formulation</h2>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The steps often followed in formulating a linear program are fairly straightforward. Here's what we will follow in this post:\n",
"\n",
"1. Parameters and data\n",
"2. Decision variables\n",
"3. Objective function\n",
"4. Constraints\n",
"5. Solve the problem"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"#import the required packages\n",
"from pulp import *\n",
"import pandas as pd"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"'''SETS'''\n",
"\n",
"#list of batch_id's waiting for production\n",
"batch_ids = ['b1', 'b2', 'b3', 'b4', 'b5']\n",
"\n",
"#list of the days available in a week\n",
"days = ['1', '2', '3', '4', '5']\n",
"\n",
"#list of shifts in a day\n",
"shifts= ['RT', 'OT']\n",
"\n",
"'''PARAMETERS'''\n",
"\n",
"#batch quantity needed\n",
"batch_size= { \n",
" 'b1': 200,\n",
" 'b2': 160,\n",
" 'b3': 120,\n",
" 'b4': 60,\n",
" 'b5': 100\n",
" }\n",
"\n",
"#regular time and over time values for all of the 6 operators combined\n",
"time_dict= {'RT': 2700, 'OT': 1800}\n",
"\n",
"#dict to store minutes available per day per shift\n",
"mins_per_day= {d: {s: time_dict[s] for s in shifts} for d in days}\n",
"\n",
"#cycle time in minutes per unit per batch\n",
"cycle_time = { \n",
" 'b1': 45,\n",
" 'b2': 30,\n",
" 'b3': 10,\n",
" 'b4': 20,\n",
" 'b5': 12\n",
" }\n",
"\n",
"'''minimum needed units per batch per day; as of now this is a fixed qty= 2, but we can create a separate\n",
"dict to store different qty per batch if needed and then use it in the dict comprehension here'''\n",
"min_qty= {d:{b: 5 for b in batch_ids} for d in days}\n",
"\n",
"pay_by_shift= {'OT': 5.175, 'RT': 3.45}\n",
"\n",
"#cost per minute per shift per day:\n",
"pay_dict= {d: {s: pay_by_shift[s] for s in shifts} for d in days}\n",
"\n",
"#indexes for batch and day combinations\n",
"shifts_ind = [(d,s) for d in days for s in shifts]\n",
"\n",
"#indexes for the make variable:\n",
"make_ind= [(d,b) for d in days for b in batch_ids]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h3>Decision Variables</h3>\n",
"\n",
"The values of the decision variables will be decided by the model as it minimizes the objective function. We want the model to tell us how many units of each batch to produce per day and we also want it to make the decision on which shift to choose. The decision variables are:\n",
"\n",
"1. <b>'make'</b>- the number of units of a given batch to be made, indexed over the available days, batches and the shifts per day. Note that we force the 'make' variables to be in the integer space. \n",
"\n",
"2. <b>'y'</b>- the 'switch' variable that the model uses to decide if a shift has to be 'on' or 'off', indexed over days and shifts. These are binary variables."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"'''VARIABLES'''\n",
"\n",
"#number of units of a batch scheduled for production per day per shift\n",
"make= LpVariable.dicts(\"make\",(days, batch_ids, shifts),0, None, cat= 'Integer')\n",
"\n",
"#binary variable to decide wether OT is scheduled on a given day or not\n",
"y= LpVariable.dicts(\"use shift\",(days, shifts), 0, 1, cat= 'Integer')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h3>Objective Function</h3>\n",
"\n",
"Our objective function consists of two parts- the first is a sum of the 'switch' variables. The second part is the cost of production which is the product of the 'make' variable, the cycle time per unit of that batch and the cost per minute it takes to manufacture in that shift. Since we want the model to tell us the best weekly schedule with the lowest total cost of production, we 'Minimize' the objective function."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"'''model formulation'''\n",
"\n",
"#create model object with a minimize objective\n",
"prob= LpProblem(\"FlexLine Problem\",LpMinimize)\n",
"\n",
"#add the objective function to the model\n",
"prob += lpSum([y[d][s] for d in days for s in shifts]) + \\\n",
" lpSum([make[d][b][s]* cycle_time[b]* pay_dict[d][s] for d in days for b in batch_ids for s in shifts]), \"Total cost per week\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h3>Constraints</h3>\n",
"\n",
"We apply the following linear constraints to our objective function for us to create a feasible region:\n",
"\n",
"1. <b>Overall Demand</b>: the model should ensure that the sum of all units produced per day for each batch for over all the days should be equal to the batch sizes.\n",
"\n",
"2. <b>Time Capacity</b>: the total time required to manufacture the units per shift per day must be less than or equal to the time available. Notice here that we multiply the switch on the righ-hand side of the equation; this is to ensure that if a shift is not switched on by the model, then no units will be produced in that shift.\n",
"\n",
"3. <b>Minimum Demand</b>: the number of units of a batch produced per day meet the minimum demand per day requirement set for that batch.\n",
"\n",
"4. <b>Linking constraint</b>: this is another constraint that ensures that if a shift is not switched on in a day, then the model cannot schedule any units to be produced in that shift.\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"'''CONSTRAINTS'''\n",
"\n",
"#demand constraint\n",
"for b in batch_ids:\n",
" prob += lpSum([make[d][b][s] for d in days for s in shifts]) == batch_size[b] \n",
" \n",
"#time constraint\n",
"for (d,s) in shifts_ind:\n",
" prob += lpSum([make[d][b][s] * cycle_time[b] for b in batch_ids]) <= mins_per_day[d][s] * y[d][s]\n",
"\n",
"#minimum per day constraint\n",
"for (d,b) in make_ind:\n",
" prob += lpSum([make[d][b][s] for s in shifts]) >= min_qty[d][b]\n",
" \n",
"#linking constraint\n",
"for (d,s) in shifts_ind:\n",
" prob += lpSum([make[d][b][s] for b in batch_ids]) <= 100000 * y[d][s]\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that when you solve the model, the message displayed says that the problem solution is 'Optimal' which means that from the set of all possible solutions, the model has found the solution that gives us the least cost (minimum) for the objective function. You can also see how I've accesses the values of the decision variables as well as the optimal value of the objective function."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Status: Optimal\n"
]
}
],
"source": [
"#solve the model and print the status\n",
"prob.solve()\n",
"print (\"Status:\", LpStatus[prob.status])"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"make_1_b1_OT = 0.0\n",
"make_1_b1_RT = 56.0\n",
"make_1_b2_OT = 55.0\n",
"make_1_b2_RT = 0.0\n",
"make_1_b3_OT = 5.0\n",
"make_1_b3_RT = 0.0\n",
"make_1_b4_OT = 5.0\n",
"make_1_b4_RT = 0.0\n",
"make_1_b5_OT = 0.0\n",
"make_1_b5_RT = 15.0\n",
"make_2_b1_OT = 0.0\n",
"make_2_b1_RT = 6.0\n",
"make_2_b2_OT = 0.0\n",
"make_2_b2_RT = 8.0\n",
"make_2_b3_OT = 0.0\n",
"make_2_b3_RT = 65.0\n",
"make_2_b4_OT = 0.0\n",
"make_2_b4_RT = 38.0\n",
"make_2_b5_OT = 0.0\n",
"make_2_b5_RT = 65.0\n",
"make_3_b1_OT = 36.0\n",
"make_3_b1_RT = 0.0\n",
"make_3_b2_OT = 1.0\n",
"make_3_b2_RT = 86.0\n",
"make_3_b3_OT = 0.0\n",
"make_3_b3_RT = 6.0\n",
"make_3_b4_OT = 7.0\n",
"make_3_b4_RT = 0.0\n",
"make_3_b5_OT = 0.0\n",
"make_3_b5_RT = 5.0\n",
"make_4_b1_OT = 0.0\n",
"make_4_b1_RT = 58.0\n",
"make_4_b2_OT = 5.0\n",
"make_4_b2_RT = 0.0\n",
"make_4_b3_OT = 0.0\n",
"make_4_b3_RT = 9.0\n",
"make_4_b4_OT = 5.0\n",
"make_4_b4_RT = 0.0\n",
"make_4_b5_OT = 5.0\n",
"make_4_b5_RT = 0.0\n",
"make_5_b1_OT = 0.0\n",
"make_5_b1_RT = 44.0\n",
"make_5_b2_OT = 0.0\n",
"make_5_b2_RT = 5.0\n",
"make_5_b3_OT = 0.0\n",
"make_5_b3_RT = 35.0\n",
"make_5_b4_OT = 0.0\n",
"make_5_b4_RT = 5.0\n",
"make_5_b5_OT = 0.0\n",
"make_5_b5_RT = 10.0\n",
"use_shift_1_OT = 1.0\n",
"use_shift_1_RT = 1.0\n",
"use_shift_2_OT = 0.0\n",
"use_shift_2_RT = 1.0\n",
"use_shift_3_OT = 1.0\n",
"use_shift_3_RT = 1.0\n",
"use_shift_4_OT = 1.0\n",
"use_shift_4_RT = 1.0\n",
"use_shift_5_OT = 0.0\n",
"use_shift_5_RT = 1.0\n"
]
}
],
"source": [
"#print the values of the variables\n",
"for v in prob.variables():\n",
" print (v.name, \"=\", v.varValue)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Total Cost of Production Per Week = 66765.5\n"
]
}
],
"source": [
"# The optimised objective function value is printed to the screen\n",
"print (\"Total Cost of Production Per Week = \", value(prob.objective))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<h3>Formatting and Saving Data</h3>\n",
"\n",
"You can use the 'writeLP' method to write the entire model formulation to a text file so that you can inspect the model. I've also written some code to format the variable data and store it as a Data Frame to make it more presentable and easier to visualize."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"#you can write the model to a text file\n",
"prob.writeLP('flexline_sol.txt')"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"results= []\n",
"\n",
"#index for creating the dataframe\n",
"make_ind2= [(d,b,s) for d in days for b in batch_ids for s in shifts]\n",
"\n",
"for d,b,s in make_ind2:\n",
" buffer= {\n",
" \n",
" 'Day': d,\n",
" 'Shift': s,\n",
" 'Shift_Status': 'On' if y[d][s].varValue == 1 else 'Off',\n",
" 'Batch_ID': b,\n",
" 'Units': make[d][b][s].varValue\n",
" }\n",
" \n",
" results.append(buffer)\n",
" \n",
"#write to the dataframe\n",
"df= pd.DataFrame.from_dict(results)\n",
"\n",
"#then use groupby to better arrange the data\n",
"df= pd.DataFrame(df.groupby(['Day', 'Shift', 'Shift_Status', 'Batch_ID'])['Units'].sum())"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"#write to an excel file\n",
"df.to_excel('schedule.xlsx')"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style>\n",
" .dataframe thead tr:only-child th {\n",
" text-align: right;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: left;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th>Units</th>\n",
" </tr>\n",
" <tr>\n",
" <th>Day</th>\n",
" <th>Shift</th>\n",
" <th>Shift_Status</th>\n",
" <th>Batch_ID</th>\n",
" <th></th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th rowspan=\"10\" valign=\"top\">1</th>\n",
" <th rowspan=\"5\" valign=\"top\">OT</th>\n",
" <th rowspan=\"5\" valign=\"top\">On</th>\n",
" <th>b1</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>55.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>5.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>5.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th rowspan=\"5\" valign=\"top\">RT</th>\n",
" <th rowspan=\"5\" valign=\"top\">On</th>\n",
" <th>b1</th>\n",
" <td>56.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>15.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th rowspan=\"10\" valign=\"top\">2</th>\n",
" <th rowspan=\"5\" valign=\"top\">OT</th>\n",
" <th rowspan=\"5\" valign=\"top\">Off</th>\n",
" <th>b1</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th rowspan=\"5\" valign=\"top\">RT</th>\n",
" <th rowspan=\"5\" valign=\"top\">On</th>\n",
" <th>b1</th>\n",
" <td>6.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>8.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>65.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>38.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>65.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th rowspan=\"10\" valign=\"top\">3</th>\n",
" <th rowspan=\"5\" valign=\"top\">OT</th>\n",
" <th rowspan=\"5\" valign=\"top\">On</th>\n",
" <th>b1</th>\n",
" <td>36.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>1.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>7.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th rowspan=\"5\" valign=\"top\">RT</th>\n",
" <th rowspan=\"5\" valign=\"top\">On</th>\n",
" <th>b1</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>86.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>6.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>5.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th rowspan=\"10\" valign=\"top\">4</th>\n",
" <th rowspan=\"5\" valign=\"top\">OT</th>\n",
" <th rowspan=\"5\" valign=\"top\">On</th>\n",
" <th>b1</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>5.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>5.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>5.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th rowspan=\"5\" valign=\"top\">RT</th>\n",
" <th rowspan=\"5\" valign=\"top\">On</th>\n",
" <th>b1</th>\n",
" <td>58.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>9.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th rowspan=\"10\" valign=\"top\">5</th>\n",
" <th rowspan=\"5\" valign=\"top\">OT</th>\n",
" <th rowspan=\"5\" valign=\"top\">Off</th>\n",
" <th>b1</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>0.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th rowspan=\"5\" valign=\"top\">RT</th>\n",
" <th rowspan=\"5\" valign=\"top\">On</th>\n",
" <th>b1</th>\n",
" <td>44.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b2</th>\n",
" <td>5.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b3</th>\n",
" <td>35.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b4</th>\n",
" <td>5.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>b5</th>\n",
" <td>10.0</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" Units\n",
"Day Shift Shift_Status Batch_ID \n",
"1 OT On b1 0.0\n",
" b2 55.0\n",
" b3 5.0\n",
" b4 5.0\n",
" b5 0.0\n",
" RT On b1 56.0\n",
" b2 0.0\n",
" b3 0.0\n",
" b4 0.0\n",
" b5 15.0\n",
"2 OT Off b1 0.0\n",
" b2 0.0\n",
" b3 0.0\n",
" b4 0.0\n",
" b5 0.0\n",
" RT On b1 6.0\n",
" b2 8.0\n",
" b3 65.0\n",
" b4 38.0\n",
" b5 65.0\n",
"3 OT On b1 36.0\n",
" b2 1.0\n",
" b3 0.0\n",
" b4 7.0\n",
" b5 0.0\n",
" RT On b1 0.0\n",
" b2 86.0\n",
" b3 6.0\n",
" b4 0.0\n",
" b5 5.0\n",
"4 OT On b1 0.0\n",
" b2 5.0\n",
" b3 0.0\n",
" b4 5.0\n",
" b5 5.0\n",
" RT On b1 58.0\n",
" b2 0.0\n",
" b3 9.0\n",
" b4 0.0\n",
" b5 0.0\n",
"5 OT Off b1 0.0\n",
" b2 0.0\n",
" b3 0.0\n",
" b4 0.0\n",
" b5 0.0\n",
" RT On b1 44.0\n",
" b2 5.0\n",
" b3 35.0\n",
" b4 5.0\n",
" b5 10.0"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"df"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the Data Frame above you can see how the model has chosen switch on or off a shift and and also how it has scheduled units of each batch to be produced. You will notice that model always chooses to switch on regular time shifts and only if it cannot meet demand based on the constraints we've applied to the model, it will choose to switch on overtime shifts. I've visualized the data as heat maps above."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.1"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment