Source: http://www.gurobi.com/resources/examples/factory-planning-I
Reference: H. Paul Williams, Model Building in Mathematical Programming, fifth edition (Pages 255-256, 350-352)
A factory makes seven products (Prod 1 to Prod 7) using a range of machines including:
Each product has a defined profit contribution per unit sold (defined as the sales price per unit minus the cost of raw materials). In addition, the manufacturing of each product requires a certain amount of time on each machine (in hours). The contribution and manufacturing time value are shown below. A dash indicates the manufacturing product for the given product does not require that machine.
PROD 1 | PROD 2 | PROD 3 | PROD 4 | PROD 5 | PROD 6 | PROD 7 | |
---|---|---|---|---|---|---|---|
Contribution to profit | 10 | 6 | 8 | 4 | 11 | 9 | 3 |
Grinding | 0.5 | 0.7 | - | - | 0.3 | 0.2 | 0.5 |
Vertical drilling | 0.1 | 0.2 | - | 0.3 | - | 0.6 | - |
Horizontal drilling | 0.2 | - | 0.8 | - | - | - | 0.6 |
Boring | 0.05 | 0.03 | 0.07 | 0.1 | - | 0.08 | |
Planing | - | - | 0.01 | - | 0.05 | - | 0.05 |
In each of the six months covered by this model, one or more of the machines is scheduled to be down for maintenance and as a result will not be available to use for production that month. The maintenance schedule is as follows:
Month | Machine |
---|---|
January | One Grinder |
February | Two Horizontal Drills |
March | One borer |
April | One vertical drill |
May | One grinder and one vertical drill |
June | One horizontal drill |
There limitations to how many of each product can be sold in a given month. These limits are shown below:
Month | PROD 1 | PROD 2 | PROD 3 | PROD 4 | PROD 5 | PROD 6 | PROD 7 |
---|---|---|---|---|---|---|---|
January | 500 | 1000 | 300 | 300 | 800 | 200 | 100 |
February | 600 | 500 | 200 | 0 | 400 | 300 | 150 |
March | 300 | 600 | 0 | 0 | 500 | 400 | 100 |
April | 200 | 300 | 400 | 500 | 200 | 0 | 100 |
May | 0 | 100 | 500 | 100 | 1000 | 300 | 0 |
June | 500 | 500 | 100 | 300 | 1100 | 500 | 60 |
Up to 100 units of each product may be stored in inventory at a cost of $0.50 per unit per month. At the start of January there is no product inventory. However, by the end of June there should be 50 units of each product in inventory.
The factory produces six days a week using two eight-hour shifts per day. It may be assumed that each month consists of 24 working days. Also, for the purposes of this model, there are no production sequencing issues that need to be taken into account.
What should the production plan look like?
Let $T$ be a set of time periods (months), where $t_0 \in T$ is the first month and $t_e \in T$ the last month.
Let $P$ be a set of products and $M$ be a set of machines.
For each month $t \in T$ and each product $p \in P$ we introduce continuous non-negative variables $b_{t,p}$, $u_{t,p}$, $s_{t,p}$.
$b_{t,p}, u_{t,p}, s_{t,p} \geq 0 ~\forall t \in T, \forall p \in P$
The objective is to maximize the profit of the company. It consists of the profit for each product minus cost for storing the unsold products. This can be stated as
$$max \sum_{t \in T} \sum_{p \in P} \left( k_p \cdot u_{t,p} - r \cdot s_{t,p} \right)$$The balance constraints ensure that the amount that is in the storage in the last month and the amount that get manufactured equals the amount that is sold and held for each product in the current month. This makes sure that all products in the model are manufactured in some month. The initial storage is empty.
$$ s_{t-1,p} + b_{t,p} = u_{t,p} + s_{t,p} ~\forall t \in T \setminus t_0,~ \forall p \in P$$$$ b_{t_0,p} = u_{t_0,p} + s_{t_0,p} ~\forall p \in P $$The endstore constraints force that at the end of the last month the storage contains the specified amount of each product (a full storage).
$$ s_{t_e,p} = z ~\forall p \in P$$The store capacity constraints restrict the amount of each product, which can be stored in each month. At most $z = 50$ units of each product be stored in each month.
$$ s_{t,p} \leq z ~\forall p \in P,~\forall t \in T $$The capacity constraints ensure that per month the time all products needs on a certain kind of machines is lower or equal than the available hours for that machine in that month multiplied by the number of available machines in that month. Each product needs some machine hours on different machines. Each machine is down in one or more months due to maintenance, so the number of available machines varies per month. There can be multiple machines per machine type.
$$ \sum_{p \in P} f_{p,m} \cdot b_{t,p} \leq g \cdot q_{t,m} ~\forall t \in T, \forall m \in M $$Import gurobipy
module:
from gurobipy import *
Define sets $P$, $M$ and $T$:
products = ["Prod1", "Prod2", "Prod3", "Prod4", "Prod5", "Prod6", "Prod7"]
months = ["Jan", "Feb", "Mar", "Apr", "May", "Jun"]
machines = ["grinder", "vertDrill", "horiDrill", "borer", "planer"]
Values for parameter $k_p$ (profit contribution per product $p \in P$):
profit_contribution = { "Prod1" : 10, "Prod2" : 6, "Prod3" : 8, "Prod4" : 4,
"Prod5" : 11, "Prod6" : 9, "Prod7" : 3 }
Alternative (shorter) definitions for products
and profit_contribution
using multidict
:
products, profit_contribution = multidict({ "Prod1" : 10, "Prod2" : 6, "Prod3" : 8, "Prod4" : 4,
"Prod5" : 11, "Prod6" : 9, "Prod7" : 3 })
Total number of machines per type:
qMachine = { "grinder" : 4, "vertDrill" : 2, "horiDrill" : 3, "borer" : 1, "planer" : 1}
Alternative (shorter definition) for machines
and qMachine
using multidict
:
machines, qMachine = multidict({ "grinder" : 4, "vertDrill" : 2, "horiDrill" : 3, "borer" : 1, "planer" : 1})
Production time required per machine type and product ($f_{p,m}$):
time_table = {
"grinder": { "Prod1": 0.5, "Prod2": 0.7, "Prod5": 0.3,
"Prod6": 0.2, "Prod7": 0.5 },
"vertDrill": { "Prod1": 0.1, "Prod2": 0.2, "Prod4": 0.3,
"Prod6": 0.6 },
"horiDrill": { "Prod1": 0.2, "Prod3": 0.8, "Prod7": 0.6 },
"borer": { "Prod1": 0.05,"Prod2": 0.03,"Prod4": 0.07,
"Prod5": 0.1, "Prod7": 0.08 },
"planer": { "Prod3": 0.01,"Prod5": 0.05,"Prod7": 0.05 }
}
Number of machines down for maintenance per month and machine type:
down = {("Jan","grinder") : 1, ("Feb", "horiDrill"): 2, ("Mar", "borer") : 1,
("Apr", "vertDrill"): 1, ("May", "grinder") : 1, ("May", "vertDrill"): 1,
("Jun", "planer") : 1, ("Jun", "horiDrill"): 1}
Sales limit per month and product:
upper_dict = {
"Jan" : { "Prod1" : 500, "Prod2" : 1000, "Prod3" : 300, "Prod4" : 300, "Prod5" : 800, "Prod6" : 200, "Prod7" : 100 },
"Feb" : { "Prod1" : 600, "Prod2" : 500, "Prod3" : 200, "Prod4" : 0, "Prod5" : 400, "Prod6" : 300, "Prod7" : 150 },
"Mar" : { "Prod1" : 300, "Prod2" : 600, "Prod3" : 0, "Prod4" : 0, "Prod5" : 500, "Prod6" : 400, "Prod7" : 100 },
"Apr" : { "Prod1" : 200, "Prod2" : 300, "Prod3" : 400, "Prod4" : 500, "Prod5" : 200, "Prod6" : 0, "Prod7" : 100 },
"May" : { "Prod1" : 0, "Prod2" : 100, "Prod3" : 500, "Prod4" : 100, "Prod5" : 1000, "Prod6" : 300, "Prod7" : 0 },
"Jun" : { "Prod1" : 500, "Prod2" : 500, "Prod3" : 100, "Prod4" : 300, "Prod5" : 1100, "Prod6" : 500, "Prod7" : 60 }
}
upper = { (month, product) : upper_dict[month][product] for month in months for product in products }
Constant parameters:
storeCost = 0.5
storeCapacity = 100
endStock = 50
hoursPerMonth = 2*8*24
Create empty named model object:
model = Model('Factory Planning')
For each product (seven kinds of products) and each time period (month) we will create variables for the amount of which products get manufactured, held and sold. In each month there is an upper limit on the amount of each product that can be sold.
Create and fill dictionaries of variables manu
($b_{t,p}$), held
($s_{t,p}$) and sell
($u_{t,p}$):
manu = model.addVars(months, products, name="manu")
held = model.addVars(months, products, name="held", ub = storeCapacity)
sell = model.addVars(months, products, name="sell", ub = upper)
Next, we create the balance constraints. The balance constraints ensure that the amount of product that is in the storage in the prior month and the amount that get manufactured equals the amount that is sold and held for each product in the current month. This makes sure that all products in the model are manufactured in some month. The initial storage is empty.
model.addConstrs((manu[months[0], product] == sell[months[0], product]
+ held[months[0], product] for product in products), name="balance")
model.addConstrs((held[months[month_index-1], product] +
manu[month, product] == sell[month, product] + held[month, product]
for product in products for month_index, month in enumerate(months)
if month != months[0]), name="balance");
The endstore constraints force that at the end of the last month the storage contains the specified amount of each product.
model.addConstrs((held[months[-1], product] == endStock for product in products), name="End_Balance");
The capacity constraints ensure that for each month the time all products need on a certain kind of machine is lower or equal than the available hours for that type of machine in that month multiplied by the number of available machines in that period. Each product needs some machine hours on different machines. Each machine is down in one or more months due to maintenance, so the number and type of available machines varies per month. There can be multiple machines per machine type.
model.addConstrs((quicksum(time_table[machine][product] * manu[month, product]
for product in time_table[machine]) <= hoursPerMonth * (qMachine[machine] -
down[month, machine]) for machine in machines for month in months
if (month, machine) in down), name = "Capacity")
model.addConstrs((quicksum(time_table[machine][product] * manu[month, product]
for product in time_table[machine]) <= hoursPerMonth * qMachine[machine]
for machine in machines for month in months
if (month, machine) not in down), name = "Capacity");
The objective is to maximize the profit of the company. It consists of the profit for each product minus cost for storing the unsold products.
obj = quicksum(
profit_contribution[product] * sell[month, product] - storeCost * held[month, product]
for month in months
for product in products
)
model.setObjective(obj, GRB.MAXIMIZE)
model.optimize()
Display solution values for all variables (with non-zero values):
model.printAttr('X')
Now, we create a nice overview per month in an HTML table:
output = "<h1>Production plan</h1><table><tr><td></td><td><b>Manufacture</b></td><td><b>Sell</b></td><td><b>Hold</b></td></tr>"
for month in months:
output += "<tr><td><b>{}</b></td><td style='text-align: right'>".format(month)
# Manufacture
for product in products:
if manu[month, product].X > 0:
output += "<b>{:.1f}</b> units of <b>{}</b><br/>".format(manu[month, product].X, product)
# Sell
output += "</td><td style='text-align: right'>"
for product in products:
if sell[month, product].X > 0:
output += "<b>{:.1f}</b> units of <b>{}</b><br/>".format(sell[month, product].X, product)
# Hold
output += "</td><td style='text-align: right'>"
for product in products:
if held[month, product].X > 0:
output += "<b>{:.1f}</b> units of <b>{}</b><br/>".format(held[month, product].X, product)
output += "</td></tr>"
output += "</table>"
from IPython.display import HTML, display
display(HTML(output))