Factory Planning I
Factory Planning I Example
Both this model and Factory Planning II 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 mix 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. Some machines are not available in every period due to maintenance. 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. In Factory Planning II, we’ll add more complexity to this example whereby the month where each machine is down will, instead of being fixed, be determined as a part of the optimized plan. Note: you can download the model, implemented in Python, here. More information on this type of model can be found in in the fifth edition of Model Building in Mathematical Programming, by H. Paul Williams.
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 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 plan 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 the product p in the month \(t\). \(u_{t,p}\) describes how much we sell of the product p in the month \(t\). \(s_{t,p}\) describes how much we store of the product p in the month \(t\). 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\) we are given the 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 month \(t \in T\) and each machine \(m \in M\) we are given the number of available machines \(q_{tm}\) given. Each machine can work \(g\) hours a month. There can be \(z\) products of each type stored in each month and storing 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} 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. \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 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 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. \begin{equation} \sum_{p \in P} f_{pm}*b_{t,p} \leq g* q_{tm} \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} \leq g* q_{tm} \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}
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 3.5.2 & 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} # 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. 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. This is due to market limitations.
model = Model('Factory Planning I') 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
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 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.
# 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 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.
# Capacity model.addConstrs((quicksum(time_table[machine][product] * manu[time_period, product] for product in time_table[machine]) <= hoursPerMonth * (qMachine[machine] - down[time_period, machine]) for machine in machines for time_period in time_periods if (time_period, machine) in down), name = "Capacity") model.addConstrs((quicksum(time_table[machine][product] * manu[time_period, product] for product in time_table[machine]) <= hoursPerMonth * qMachine[machine] for machine in machines for time_period in time_periods if (time_period, 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. 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-i-output.sol")
Gurobi Output and Analysis
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.00s 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.01 seconds Optimal objective 9.371517857e+04
Analyzing the Output
This policy yields a total profit of $93 715.
Manufacture | Sell | Hold | |
---|---|---|---|
January | 500 PROD 1 888.6 PROD 2 382.5 PROD 3 300 PROD 4 800 PROD 5 200 PROD 6 | 500 PROD 1 888.6 PROD 2 300 PROD 3 300 PROD 4 800 PROD 5 200 PROD 6 | 82.5 PROD 3 |
February | 700 PROD 1 600 PROD 2 117.5 PROD 3 500 PROD 5 300 PROD 6 250 PROD 7 | 600 PROD 1 500 PROD 2 200 PROD 3 400 PROD 5 300 PROD 6 150 PROD 7 | 100 PROD 1 100 PROD 2 100 PROD 5 100 PROD 7 |
March | 400 PROD 6 | 100 PROD 1 100 PROD 2 100 PROD 5 400 PROD 6 100 PROD 7 | Nothing |
April | 200 PROD 1 300 PROD 2 400 PROD 3 500 PROD 4 200 PROD 5 100 PROD 7 | 200 PROD 1 300 PROD 2 400 PROD 3 500 PROD 4 200 PROD 5 100 PROD 7 | Nothing |
May | 100 PROD 2 600 PROD 3 100 PROD 4 1100 PROD 5 300 PROD 6 100 PROD 7 | 100 PROD 2 500 PROD 3 100 PROD 4 1000 PROD 5 300 PROD 6 | 100 PROD 3 100 PROD 5 100 PROD 7 |
June | 550 PROD 1 550 PROD 2 350 PROD 4 550 PROD 6 | 500 PROD 1 500 PROD 2 50 PROD 3 300 PROD 4 50 PROD 5 500 PROD 6 50 PROD 7 | 50 of every product (stipulated) |