Example problem: multi-item, multi-period production planning

The company Coco has two plants that can produce two types of cocoa powder. The first factory has a total capacity of 400 tons per month and the second of 500 tons per month. The marketing department has provided estimations for the maximum amount of every product that may be sold in each of the next four months, and also the expected sales prices. Several raw materials are used in the production with known raw material requirements per ton of finished products. Finished products and raw material may be stored at the factories from one tim period to the next, incurring a given cost per ton and per time period. The raw material storage capacity at the factories is limited to 300 tons. How should the two plants be operated during the planning period to maximize the total profit?

Original model

Let PRODS be the set of finished products, FACT the set of factories, RAW the set of raw materials, and TIMES={1,...,NT} the set of time periods under consideration.

We define decision variables make_pft representing the quantity of product p made at factory f during time period t. Furthermore, to model the transition from one time period to the next and to account for the different types of cost incurred, we need several other sets of variables: sell_pft, the amount of product p sold at factory f in period t; buy_rft the amount of raw material r bought at f in t; and finally pstock_pft and rstock_rft (both defined for t=1,...,NT+1) respectively the amount of product and raw material held in stock at factory f at the beginning of period t.

Let further MXSELL_pt be the maximum sales quantity of product p in period t, MXMAKE_f the capacity limit of factory f, and MXRSTOCK the raw material storage capacity.

Let IPSTOCK_pf be the quantity of product p initially held in stock at factory f and IRSTOCK_rf the initial stock level of raw material r. We denote by CPSTOCK and CRSTOCK respectively the unit cost for storing finished product and raw material.

The objective function of maximizing the total profit is to maximize the sales revenues (REV_p), minus the cost of production (CMAKE_pf), buying raw material (CBUY_rt), and storing finished products and raw material.

The possibility to store products between time periods gives rise to three sets of constraints: the inventory balance constraints for finished products (PBal_pft) and for raw material (RBal_rft), and the limit on the raw material storage capacity (MxRStock_ft). The stock pstock_p,f,t+1 of product p at the beginning of t+1 is given by the stock at the beginning of t plus the production in t reduced by the amount sold on t. The stock rstock_r,f,t+1 of raw material r at the beginning of t+1 is given by the corresponding stock at the beginning of t plus the amount bought in t reduced by the quantity used in production during t.

∀ p ∈ PRODS, ∀ f ∈ FACT, ∀ t ∈ TIME: PBal_pft:= pstock_p,f,t+1 = pstock_pft + make_pft - sell_pft
∀ r ∈ RAW, ∀ f ∈ FACT, ∀ t ∈ TIME:
RBal_rft:= rstock_r,f,t+1 = rstock_rft + buy_rft -

∑

_{p ∈ PRODS}

REQ_pr · make_pft
∀ f ∈ FACT, ∀ t ∈ {2,...,NT+1}: MxRStock_ft:=

∑

_{r ∈ RAW}

rstock_rft ≤ MXRSTOCK

We further have two sets of capacity constraints: the production capacity of the factories is limited (constraints MxMake_ft) and we can only sell up to a given maximum amount of finished products per time period (constraints MxSell_ft).

Below the complete mathematical model is given. The initial stock levels (t=1) of finished products and raw material are fixed to the given values.

maximize

∑

_{p ∈ PRODS}

∑

_{f ∈ FACT}

∑

_{t ∈ TIME}

REV_pt · sell_pft
-

∑

_{p ∈ PRODS}

∑

_{f ∈ FACT}

∑

_{t ∈ TIME}

CMAKE_pf · make_pft -

∑

_{r ∈ RAW}

∑

_{f ∈ FACT}

∑

_{t ∈ TIME}

CBUY_rt · buy_rft
-

∑

_{p ∈ PRODS}

∑

_{f ∈ FACT}

^NT+1

∑

_{t =2}

CPSTOCK · pstock_pft -

∑

_{r ∈ RAW}

∑

_{f ∈ FACT}

^NT+1

∑

_{t =2}

CRSTOCK · rstock_rft
∀ p ∈ PRODS, ∀ f ∈ FACT, ∀ t ∈ TIME: PBal_pft:= pstock_p,f,t+1 = pstock_pft + make_pft - sell_pft
∀ r ∈ RAW, ∀ f ∈ FACT, ∀ t ∈ TIME:
RBal_rft:= rstock_r,f,t+1 = rstock_rft + buy_rft -

∑

_{p ∈ PRODS}

REQ_pr · make_pft
∀ p ∈ PRODS, ∀ t ∈ TIME: MxSell_pt:=

∑

_{f ∈ FACT}

sell_pft ≤ MXSELL_p
∀ f ∈ FACT, ∀ t ∈ TIME: MxMake_ft:=

∑

_{p ∈ PRODS}

make_pft ≤ MXMAKE_f
∀ f ∈ FACT, ∀ t ∈ {2,...,NT+1}: MxRStock_ft:=

∑

_{r ∈ RAW}

rstock_rft ≤ MXRSTOCK
∀ p ∈ PRODS, ∀ f ∈ FACT: pstock_pf1 = IPSTOCK_pf
∀ r ∈ RAW, ∀ f ∈ FACT: rstock_rf1 = IRSTOCK_rf
∀ p ∈ PRODS, ∀ f ∈ FACT, ∀ t ∈ TIME: make_pft≥ 0, sell_pft≥ 0
∀ r ∈ RAW, ∀ f ∈ FACT, ∀ t ∈ TIME: buy_rft ≥ 0
∀ p ∈ PRODS, ∀ f ∈ FACT, ∀ t ∈ {1,...,NT+1}: pstock_pft ≥ 0
∀ r ∈ RAW, ∀ f ∈ FACT, ∀ t ∈ {1,...,NT+1}: rstock_rft ≥ 0

Problem decomposition

We now decompose the problem described above according to production locations. Notice that this is not the only way of decomposing this problem: we may just as well choose a decomposition by products or by time periods. However, both of these choices result in a larger number of global constraints than the decomposition by factories, meaning that the master problem may become more difficult to solve.

For every factory f we obtain the following subproblem (including the sales limit constraints MxSell in the form of bounds in the submodels is not required, but may lead to better, that is, more exact or faster solutions).

maximize

∑

_{p ∈ PRODS}

∑

_{t ∈ TIME}

REV_pt · sell_pt
-

∑

_{p ∈ PRODS}

∑

_{t ∈ TIME}

CMAKE_p · make_pt -

∑

_{r ∈ RAW}

∑

_{t ∈ TIME}

CBUY_rt · buy_rt
-

∑

_{p ∈ PRODS}

^NT+1

∑

_{t =2}

CPSTOCK · pstock_pt -

∑

_{r ∈ RAW}

^NT+1

∑

_{t =2}

CRSTOCK · rstock_rt
∀ p ∈ PRODS, ∀ t ∈ TIME: PBal_pt:= pstock_p,t+1 = pstock_pt + make_pt - sell_pt
∀ r ∈ RAW, ∀ t ∈ TIME: RBal_rt:= rstock_r,t+1 = rstock_rt + buy_rt -

∑

_{p ∈ PRODS}

REQ_pr · make_pt
∀ t ∈ TIME: MxMake_t:=

∑

_{p ∈ PRODS}

make_pt ≤ MXMAKE
∀ t ∈ {2,...,NT+1}: MxRStock_t:=

∑

_{r ∈ RAW}

rstock_rt ≤ MXRSTOCK
∀ p ∈ PRODS, ∀ t ∈ TIME: MxSell_pt:= sell_pt ≤ MXSELL_p
∀ p ∈ PRODS: pstock_p1 = IPSTOCK_p
∀ r ∈ RAW: rstock_r1 = IRSTOCK_r
∀ p ∈ PRODS, ∀ t ∈ TIME: make_pt≥ 0, sell_pt≥ 0
∀ r ∈ RAW, ∀ t ∈ TIME: buy_rt ≥ 0
∀ p ∈ PRODS, ∀ t ∈ {1,...,NT+1}: pstock_pt ≥ 0
∀ r ∈ RAW, ∀ t ∈ {1,...,NT+1}: rstock_rt ≥ 0

The master problem only contains a single set of global constraints, namely the sales limit constraints MxSell (for clarity's sake, the non-negativity constraints are left out here).

In the decomposition algorithm, the decision variables in the master problem are expressed via the solutions (proposals) generated by the subproblems, such as

∀ p ∈ PRODS, ∀ f ∈ FACT, ∀ t ∈ TIME: sell_pft =

^nPROP_f

∑

_k=1

Prop_sell_pftk·weight_fk

where Prop_sell_pftk stands for the solution value of variable sell_pt in the k^th proposal generated by subproblem f and Prop_cost_fk is the objective value this proposal. For every subproblem f we need to add a convexity constraint Convex_f on the weight_fk variables.

maximize

∑

_{f ∈ FACT}

^nPROP_f

∑

_k=1

Prop_cost_fk·weight_fk
∀ p ∈ PRODS, ∀ t ∈ TIME: MxSell_pt:=

∑

_{f ∈ FACT}

^nPROP_f

∑

_k=1

Prop_sell_pftk·weight_fk ≤ MXSELL_p
∀ f ∈ FACT: Convex_f:=

^nPROP_f

∑

_k=1

weight_fk = 1
∀ f ∈ FACT, ∀ k ∈ 1,...,nPROP_f: weight_fk≥ 0

We shall refer to this problem as the modified master problem. Without going any further into technical detail we simply remark that a correspondence exists between the solution of the original problem and those of the modified master problem.

Contents

Index

Glossary

Search Results

Example problem: multi-item, multi-period production planning

Original model

Problem decomposition