Demo 3 - Factory Planning

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)

Problem Description

A factory makes seven products (Prod 1 to Prod 7) using a range of machines including:

  • Four grinders
  • Two vertical drills
  • Three horizontal drills
  • One borer
  • One planer

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?

Model Formulation

Sets

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.

Parameters

  • For each product $p \in P$ and each type of machine $m \in M$ we are given the time $f_{p,m}$ (in hours) the product $p \in P$ needs to be manufactured on the machine $m \in M$.
  • For each month $t \in T$ and each product $p \in P$ we are given the upper limit on sales of $l_{t,p}$ for that product in that month.
  • For each product $p \in P$ we are given the profit $k_p$.
  • For each month $t \in T$ and each machine $m \in M$ we are given the number of available machines $q_{t,m}$.
  • Each machine can work $g$ hours a month.
  • There can be $z$ products of each type stored in each month and storing costs $r$ per product per month occur.

Variables

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}$ describes how much we produce of the product $p$ in the month $t \in T$.
  • $u_{t,p}$ describes how much we sell of the product $p \in P$ in the month $t \in T$.
  • $s_{t,p}$ describes how much we store of the product $p \in P$ in the month $t \in T$.

$b_{t,p}, u_{t,p}, s_{t,p} \geq 0 ~\forall t \in T, \forall p \in P$

Objective function

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)$$

Constraints

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 $$

Python Implementation

Import gurobipy module:

In [1]:
from gurobipy import *

Data definition

Define sets $P$, $M$ and $T$:

In [2]:
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$):

In [3]:
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:

In [4]:
products, profit_contribution = multidict({ "Prod1" : 10, "Prod2" : 6, "Prod3" : 8, "Prod4" : 4, 
                                            "Prod5" : 11, "Prod6" : 9, "Prod7" : 3 })

Total number of machines per type:

In [5]:
qMachine = { "grinder" : 4, "vertDrill" : 2, "horiDrill" : 3, "borer" : 1, "planer" : 1}

Alternative (shorter definition) for machines and qMachine using multidict:

In [6]:
machines, qMachine = multidict({ "grinder" : 4, "vertDrill" : 2, "horiDrill" : 3, "borer" : 1, "planer" : 1})

Production time required per machine type and product ($f_{p,m}$):

In [7]:
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:

In [8]:
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:

In [9]:
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:

In [10]:
storeCost = 0.5
storeCapacity = 100
endStock = 50
hoursPerMonth = 2*8*24

Model Generation

Create empty named model object:

In [11]:
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}$):

In [12]:
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.

In [13]:
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.

In [14]:
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.

In [15]:
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.

In [16]:
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)

Solving the model

In [17]:
model.optimize()
Optimize a model with 79 rows, 126 columns and 288 nonzeros
Coefficient statistics:
  Matrix range     [1e-02, 1e+00]
  Objective range  [5e-01, 1e+01]
  Bounds range     [6e+01, 1e+03]
  RHS range        [5e+01, 2e+03]
Presolve removed 74 rows and 110 columns
Presolve time: 0.01s
Presolved: 5 rows, 16 columns, 21 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    9.4425000e+04   1.440000e+02   0.000000e+00      0s
       2    9.3715179e+04   0.000000e+00   0.000000e+00      0s

Solved in 2 iterations and 0.02 seconds
Optimal objective  9.371517857e+04

Display solution values for all variables (with non-zero values):

In [18]:
model.printAttr('X')
    Variable            X 
-------------------------
manu[Jan,Prod1]          500 
manu[Jan,Prod2]      888.571 
manu[Jan,Prod3]        382.5 
manu[Jan,Prod4]          300 
manu[Jan,Prod5]          800 
manu[Jan,Prod6]          200 
manu[Feb,Prod1]          700 
manu[Feb,Prod2]          600 
manu[Feb,Prod3]        117.5 
manu[Feb,Prod5]          500 
manu[Feb,Prod6]          300 
manu[Feb,Prod7]          250 
manu[Mar,Prod6]          400 
manu[Apr,Prod1]          200 
manu[Apr,Prod2]          300 
manu[Apr,Prod3]          400 
manu[Apr,Prod4]          500 
manu[Apr,Prod5]          200 
manu[Apr,Prod7]          100 
manu[May,Prod2]          100 
manu[May,Prod3]          600 
manu[May,Prod4]          100 
manu[May,Prod5]         1100 
manu[May,Prod6]          300 
manu[May,Prod7]          100 
manu[Jun,Prod1]          550 
manu[Jun,Prod2]          550 
manu[Jun,Prod4]          350 
manu[Jun,Prod6]          550 
held[Jan,Prod3]         82.5 
held[Feb,Prod1]          100 
held[Feb,Prod2]          100 
held[Feb,Prod5]          100 
held[Feb,Prod7]          100 
held[May,Prod3]          100 
held[May,Prod5]          100 
held[May,Prod7]          100 
held[Jun,Prod1]           50 
held[Jun,Prod2]           50 
held[Jun,Prod3]           50 
held[Jun,Prod4]           50 
held[Jun,Prod5]           50 
held[Jun,Prod6]           50 
held[Jun,Prod7]           50 
sell[Jan,Prod1]          500 
sell[Jan,Prod2]      888.571 
sell[Jan,Prod3]          300 
sell[Jan,Prod4]          300 
sell[Jan,Prod5]          800 
sell[Jan,Prod6]          200 
sell[Feb,Prod1]          600 
sell[Feb,Prod2]          500 
sell[Feb,Prod3]          200 
sell[Feb,Prod5]          400 
sell[Feb,Prod6]          300 
sell[Feb,Prod7]          150 
sell[Mar,Prod1]          100 
sell[Mar,Prod2]          100 
sell[Mar,Prod5]          100 
sell[Mar,Prod6]          400 
sell[Mar,Prod7]          100 
sell[Apr,Prod1]          200 
sell[Apr,Prod2]          300 
sell[Apr,Prod3]          400 
sell[Apr,Prod4]          500 
sell[Apr,Prod5]          200 
sell[Apr,Prod7]          100 
sell[May,Prod2]          100 
sell[May,Prod3]          500 
sell[May,Prod4]          100 
sell[May,Prod5]         1000 
sell[May,Prod6]          300 
sell[Jun,Prod1]          500 
sell[Jun,Prod2]          500 
sell[Jun,Prod3]           50 
sell[Jun,Prod4]          300 
sell[Jun,Prod5]           50 
sell[Jun,Prod6]          500 
sell[Jun,Prod7]           50 

Now, we create a nice overview per month in an HTML table:

In [19]:
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))

Production plan

ManufactureSellHold
Jan500.0 units of Prod1
888.6 units of Prod2
382.5 units of Prod3
300.0 units of Prod4
800.0 units of Prod5
200.0 units of Prod6
500.0 units of Prod1
888.6 units of Prod2
300.0 units of Prod3
300.0 units of Prod4
800.0 units of Prod5
200.0 units of Prod6
82.5 units of Prod3
Feb700.0 units of Prod1
600.0 units of Prod2
117.5 units of Prod3
500.0 units of Prod5
300.0 units of Prod6
250.0 units of Prod7
600.0 units of Prod1
500.0 units of Prod2
200.0 units of Prod3
400.0 units of Prod5
300.0 units of Prod6
150.0 units of Prod7
100.0 units of Prod1
100.0 units of Prod2
100.0 units of Prod5
100.0 units of Prod7
Mar400.0 units of Prod6
100.0 units of Prod1
100.0 units of Prod2
100.0 units of Prod5
400.0 units of Prod6
100.0 units of Prod7
Apr200.0 units of Prod1
300.0 units of Prod2
400.0 units of Prod3
500.0 units of Prod4
200.0 units of Prod5
100.0 units of Prod7
200.0 units of Prod1
300.0 units of Prod2
400.0 units of Prod3
500.0 units of Prod4
200.0 units of Prod5
100.0 units of Prod7
May100.0 units of Prod2
600.0 units of Prod3
100.0 units of Prod4
1100.0 units of Prod5
300.0 units of Prod6
100.0 units of Prod7
100.0 units of Prod2
500.0 units of Prod3
100.0 units of Prod4
1000.0 units of Prod5
300.0 units of Prod6
100.0 units of Prod3
100.0 units of Prod5
100.0 units of Prod7
Jun550.0 units of Prod1
550.0 units of Prod2
350.0 units of Prod4
550.0 units of Prod6
500.0 units of Prod1
500.0 units of Prod2
50.0 units of Prod3
300.0 units of Prod4
50.0 units of Prod5
500.0 units of Prod6
50.0 units of Prod7
50.0 units of Prod1
50.0 units of Prod2
50.0 units of Prod3
50.0 units of Prod4
50.0 units of Prod5
50.0 units of Prod6
50.0 units of Prod7