Factory Planning II

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.

Instead of pre-defining a maintenance schedule for the machines, as was done in Factory Planning I, in this version of the model we will also optimize for the maintenance schedule.

The maintenance requirements are as follows:

• Each machine must be down for maintenance in one month of the six.
• The exception to the above are the grinding machines where only two of them need to be down during the six months.

There limitations to how many of each product can be sold in a given month. These limits are shown below:

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 product 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 and maintenance plans look like? Also, recommend any price increases and identify the value of acquiring any new machines.

This problem is based on a larger model built for the Cornish engineering company of Holman Brothers.

Model Formulation

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

For each month \(t \in T\) and each machine \(m \in M\) we introduce an integer variable \(d\), which describes how many of this type of machine is down in the month.

For each product \(p \in P\) and each type of machine \(m \in M\) we are given the time \(f_{pm}\) (in hours) the product \(p\) needs to be manufactured on the machine \(m\).

For each month \(t \in T\) and each product \(p \in P\) there is an upper limit on sales of \(l_{tp}\) for that product in that month. For each product \(p \in P\) we are given the profit for each product \(k_p\).

For each machine \(m \in M\) we are given the number of machines \(q_{m}\). Each machine can work \(g\) hours a month. Also, there needs \(k_{m}\) many of each machine down in a month.

There can be \(z\) products of each type stored in each month and storage cost \(r\) per product per month occur.

The variables can be formulated as:
\begin{equation}
b_{t,o},u_{t,o},s_{t,o} \geq 0 \quad \forall t \in T, \ \forall p \in P
\end{equation}

\begin{equation}
0 \leq d_{t,m} \leq k_{m}, d_{t,m} \in \mathbb{Z} \quad \forall t \in T, \ \forall m \in M
\end{equation}

The balance constraints ensure that the amount that is in the storage in the last mmonth 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.

\begin{equation}
s_{t-1,p} + b_{t,p} = u_{t,p}+ s_{t,p} \quad \forall t \in T \setminus t_0, \ \forall p \in P
\end{equation}

\begin{equation}
b_{t_0,p} = u_{t_0,p} + s_{t_0,p} \quad \forall p \in P.
\end{equation}

The endstore constraints force that at the end of the last month the storage contains the specified amount of each product (a full storage).

\begin{equation}
s_{t_e,p} = z \quad \forall p \in P.
\end{equation}

The store capacity constraints restrict the amount of each product which can be stored in each month. At most 50 units of each product can be stored in each month.

\begin{equation}
s_{t,p} \leq z \quad \forall p \in P, \forall t \in T.
\end{equation}

The capacity constraints ensure that per month the time all products need on a certain kind of machine is
lower or equal than the available hours for this 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 some month due to maintenance, so the availability of machines varies per month. There can be multiple machines per machine type.

\begin{equation}
\sum_{p \in P} f_{pm}*b_{t,p} + g*d_{tm} \leq g*q_{tm} \quad \forall t \in T, \quad \forall m \in M.
\end{equation}

The must-be-down constraints ensure that the specified amount of each machine is down due maintaince in some month. Which month it is down is now part of the optimization.

\begin{equation}
\sum_{t \in T} d_{tm} = k_{m} \quad \forall m \in M.
\end{equation}

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
\begin{equation}
\max \sum_{t \in T} \sum_{p \in P} k_p * u_{t,p} – r * s_{t,p}.
\end{equation}

The full model can be stated as
\begin{equation}
\max \sum_{t \in T} \sum_{p \in P} k_p * u_{t,p} – r * s_{t,p}
\end{equation}

\begin{equation}
s_{t-1,p} + b_{t,p} = u_{t,p}+ s_{t,p} \quad \forall t \in T \setminus t_0, \ \forall p \in P
\end{equation}

\begin{equation}
b_{t_0,p} = u_{t_0,p} + s_{t_0,p} \quad \forall p \in P.
\end{equation}

\begin{equation}
s_{t_e,p} = z \quad \forall p \in P.
\end{equation}

\begin{equation}
s_{t,p} \leq z \quad \forall p \in P, \forall t \in T.
\end{equation}

\begin{equation}
\sum_{p \in P} f_{pm}*b_{t,p} + g*d_{tm} \leq g*q_{tm} \quad \forall t \in T, \quad \forall m \in M.
\end{equation}

\begin{equation}
\sum_{t \in T} d_{tm} = (q_{m}-k_{m}) \quad \forall t \in T, \quad \forall m \in M.
\end{equation}

\begin{equation}
b_{t,o},u_{t,o},s_{t,o} \geq 0 \quad \forall t \in T, \ \forall p \in P
\end{equation}

\begin{equation}
0 \leq d_{t,m} \leq k_{m}, d_{t,m} \in \mathbb{Z} \quad \forall t \in T, \ \forall m \in M
\end{equation}

Implementation with comments

First, we import the Gurobi Python Module and initialize the data structures with the given data.

from gurobipy import *

# tested with Python 2.7.6 & Gurobi 7.0.1

products = ["Prod1", "Prod2", "Prod3", "Prod4", "Prod5", "Prod6", "Prod7"]
machines = ["grinder", "vertDrill", "horiDrill", "borer", "planer"]
time_periods = ["January", "February", "March", "April", "May", "June"]

profit_contribution = {"Prod1":10, "Prod2":6, "Prod3":8, "Prod4":4, "Prod5":11, "Prod6":9, "Prod7":3}

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
down = {("January","grinder"): 1, ("February", "horiDrill"): 2, ("March", "borer"): 1,
        ("April", "vertDrill"): 1, ("May", "grinder"): 1, ("May", "vertDrill"): 1,
        ("June", "planer"): 1, ("June", "horiDrill"): 1}

# number of each machine available
qMachine = {"grinder":4, "vertDrill":2, "horiDrill":3, "borer":1, "planer":1} 
# number of machines that need to be under maintenance
qMaintenance = {"grinder":2, "vertDrill":2, "horiDrill":3, "borer":1, "planer":1} 

# market limitation of sells
upper = {
    ("January", "Prod1") : 500,
    ("January", "Prod2") : 1000,
    ("January", "Prod3") : 300,
    ("January", "Prod4") : 300,
    ("January", "Prod5") : 800,
    ("January", "Prod6") : 200,
    ("January", "Prod7") : 100,
    ("February", "Prod1") : 600,
    ("February", "Prod2") : 500,
    ("February", "Prod3") : 200,
    ("February", "Prod4") : 0,
    ("February", "Prod5") : 400,
    ("February", "Prod6") : 300,
    ("February", "Prod7") : 150,
    ("March", "Prod1") : 300,
    ("March", "Prod2") : 600,
    ("March", "Prod3") : 0,
    ("March", "Prod4") : 0,
    ("March", "Prod5") : 500,
    ("March", "Prod6") : 400,
    ("March", "Prod7") : 100,
    ("April", "Prod1") : 200,
    ("April", "Prod2") : 300,
    ("April", "Prod3") : 400,
    ("April", "Prod4") : 500,
    ("April", "Prod5") : 200,
    ("April", "Prod6") : 0,
    ("April", "Prod7") : 100,
    ("May", "Prod1") : 0,
    ("May", "Prod2") : 100,
    ("May", "Prod3") : 500,
    ("May", "Prod4") : 100,
    ("May", "Prod5") : 1000,
    ("May", "Prod6") : 300,
    ("May", "Prod7") : 0,
    ("June", "Prod1") : 500,
    ("June", "Prod2") : 500,
    ("June", "Prod3") : 100,
    ("June", "Prod4") : 300,
    ("June", "Prod5") : 1100,
    ("June", "Prod6") : 500,
    ("June", "Prod7") : 60,
}


storeCost = 0.5
storeCapacity = 100
endStock = 50
hoursPerMonth = 2*8*24

Next, we create a model and the variables. We set the UpdateMode parameter to 1 (which simplifies the code – see the documentation for more details). For each product (seven kinds of products) and each time period (month) we will create variables for the amount of which products will get manufactured, held and sold. In each month there is an upper limit on the amount of each product that can be sold. This is due to market limitations. For each type of machine and each month we create a variable d, which tells us how many machines are down in this month of this type.

model = Model('Factory Planning II')
model.Params.UpdateMode = 1

manu = model.addVars(time_periods, products, name="Manu") # quantity manufactured
held = model.addVars(time_periods, products, ub=storeCapacity, name="Held") # quantity stored
sell = model.addVars(time_periods, products, ub=upper, name="Sell") # quantity sold
d = model.addVars(time_periods, machines,vtype=GRB.INTEGER, name="d") # number of machines down

Next, we insert the constraints.
The balance constraints ensure that the amount of product that is in the storage in the prior month and the amount that gets 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.

#Initial Balance
model.addConstrs((manu[time_periods[0], product] == sell[time_periods[0], product] 
                  + held[time_periods[0], product] for product in products), name="Initial_Balance")
    
#Balance
model.addConstrs((held[time_periods[time_periods.index(time_period) -1], product] 
    + manu[time_period, product] == sell[time_period, product] + held[time_period, product] 
    for product in products for time_period in time_periods if time_period != time_periods[0]), name="Balance")

The endstore constraints force that at the end of the last month the storage contains the specified amount of each product.

#End store
model.addConstrs((held[time_periods[-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 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 and types of available machines varies per month. There can be multiple machines per machine type.

#Capacity
model.addConstrs((quicksum(time_table[machine][product] * manu[time_period, product] 
	for product in time_table[machine]) <= hoursPerMonth * (qMachine[machine] - d[time_period, machine]) 
	for machine in machines for time_period in time_periods), name = "Capacity")

The Maintenance constraints ensure that the specified number and types of machines are down due maintaince in some month. Which month a machine is down is down is now part of the optimization.

#Maintenance
model.addConstrs((d.sum('*', machine) == qMaintenance[machine] for machine in machines), "Maintenance")

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:

#Objective
obj = quicksum(profit_contribution[product] * sell[time_period, product] -  
	storeCost * held[time_period, product]  
	for time_period in time_periods for product in products)

model.setObjective(obj, GRB.MAXIMIZE)

Next, we start the optimization and Gurobi tries to find the optimal solution.

model.optimize()
for v in model.getVars():
    if v.X != 0:
        print("%s %f" % (v.Varname, v.X))

Note: If you want to write your solution to a file, rather than print it to the terminal, you can use the model.write() command. An example implementation is:

model.write("factory-planning-ii-output.sol")

Gurobi Output and Analysis

Changed value of parameter UpdateMode to 1
   Prev: 0  Min: 0  Max: 1  Default: 0
Optimize a model with 84 rows, 156 columns and 348 nonzeros
Coefficient statistics:
  Matrix range    [1e-02, 4e+02]
  Objective range [5e-01, 1e+01]
  Bounds range    [1e+00, 1e+03]
  RHS range       [1e+00, 2e+03]
Found heuristic solution: objective -175
Presolve removed 22 rows and 27 columns
Presolve time: 0.00s
Presolved: 62 rows, 129 columns, 278 nonzeros
Variable types: 105 continuous, 24 integer (12 binary)

Root relaxation: objective 1.164550e+05, 15 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 116455.000    0   15 -175.00000 116455.000      -     -    0s
H    0     0                    92755.000000 116455.000  25.6%     -    0s
H    0     0                    94881.666667 116455.000  22.7%     -    0s
H    0     0                    107761.66667 116455.000  8.07%     -    0s
     0     0 111866.514    0    8 107761.667 111866.514  3.81%     -    0s
H    0     0                    108776.66667 111866.514  2.84%     -    0s
     0     0 110654.317    0    7 108776.667 110654.317  1.73%     -    0s
H    0     0                    108855.00000 110654.317  1.65%     -    0s
     0     0 109034.153    0    8 108855.000 109034.153  0.16%     -    0s
     0     0     cutoff    0      108855.000 108855.000  0.00%     -    0s

Cutting planes:
  Gomory: 4
  Implied bound: 15
  MIR: 3

Explored 0 nodes (84 simplex iterations) in 0.01 seconds
Thread count was 8 (of 8 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 1.088550000000e+05, best bound 1.088550000000e+05, gap 0.0%

Analyzing the Output

This plan results in a total profit of $108 855.
This reflects a gain of $15 140 over the course of six months vs. the Factory Planning I example as a result of seeking an optimal maintenance schedule instead of the one imposed in that example.