Both this model and Factory Planning I are examples of production planning problems. In production planning problems, choices must be made about how many of what products to produce using what resources in order to maximize profits or minimize costs, while meeting a range of constraints. These problems are common across a broad range of manufacturing situations.
In this particular example, we’ll model and solve a production planning problem: during each period we can manufacture a range of products. Each of the products needs a different amount of time to manufacture on different machines, and yields a different profit.The aim is to create an optimal multi-period production plan to maximize the profit. Different from the Factory Planning I example, in this example the month where each machine is down will, instead of being fixed, be determined as part of the optimized plan. There is a upper limit on the sales of each product in each month due to market limitations and the storage capacity is also restricted.
Note: you can download the model, implemented in Python, here. More information on this type of model can be found in the fifth edition of Model Building in Mathematical Programming, by H. Paul Williams.
H. Paul Williams, Model Building in Mathematical Programming, fifth edition (Page 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 |
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:
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 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.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 a binary 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} = (q_{m}-k_{m}) \quad \forall t \in T, \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}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")
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%
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.
Manufacture | Sell | Hold | |
---|---|---|---|
January | 500 PROD 1 |
500 PROD 1 1000 PROD 2 300 PROD 3 300 PROD 4 800 PROD 5 200 PROD 6 100 PROD 7 |
Nothing |
February | 600 PROD 1 500 PROD 2 200 PROD 3 400 PROD 5 300 PROD 6 150 PROD 7 |
600 PROD 1 500 PROD 2 200 PROD 3 400 PROD 5 300 PROD 6 150 PROD 7 |
Nothing |
March | 400 PROD 1 700 PROD 2 100 PROD 3 100 PROD 4 600 PROD 5 400 PROD 6 200 PROD 7 |
300 PROD 1 600 PROD 2 500 PROD 5 400 PROD 6 100 PROD 7 |
100 PROD 1 100 PROD 2 100 PROD 3 100 PROD 4 100 PROD 5 100 PROD 7 |
April | 100 PROD 2 100 PROD 3 100 PROD 4 100 PROD 5 100 PROD 7 |
100 PROD 1 100 PROD 2 100 PROD 3 100 PROD 4 100 PROD 5 100 PROD 7 |
Nothing |
May | 100 PROD 2 500 PROD 3 100 PROD 4 1000 PROD 5 300 PROD 6 |
100 PROD 2 500 PROD 3 100 PROD 4 1000 PROD 5 300 PROD 6 |
Nothing |
June | 550 PROD 1 550 PROD 2 150 PROD 3 350 PROD 4 1150 PROD 5 550 PROD 6 110 PROD 7 |
500 PROD 1 500 PROD 2 100 PROD 3 300 PROD 4 1100 PROD 5 500 PROD 6 60 PROD 7 |
50 of every product (stipulated) |