Production planning under demand uncertainty

Topics covered in this section:

Problem description

As the manager of a plant producing drinking glasses you wish to plan the production for the next 12 weeks. Your plant produces six different types (V1 to V6) in batches of 1000 glasses; batches may be incomplete (fewer than 1000 glasses). For every glass type you have got demand estimate for the 12 coming weeks. The initial stock and as well as the required final stock level (in thousands) are known. Per batch of every glass type, the production and storage costs in € are given, together with the required working time for workers and machines (in hours), and the required storage space (measured in numbers of trays).

Mathematical formulation

Multi-period, multi-item production planning problem

Let PRODS be the set of products (glass types) and WEEKS = {1,...,NT} the set of time periods. We write DEM_pt for the demand for product p in time period t. We also have CPROD_p and CSTOCK_p the production and storage cost for glass type p. This cost is identical for all time periods, but it would be easy to model a different cost per time period by adding an index for the time period.

TIMEW_p and TIMEM_p denote the worker and machine times respectively required per unit of product p, and correspondingly, SPACE_p the storage area. The initial stock ISTOCK_p is given, as is the desired final stock level FSTOCK_p per product (see data in Table Data for six glass types). We write CAPW and CAPM for the capacities of workers and machines respectively, and CAPS for the capacity of the storage area.

To solve this problem, we need variables produce_pt to represent the production of glass type p in time period t. The variables corresponding to the stock level of every product p at the end of period t are called store_pt. By convention, the initial stock level ISTOCK_p may be considered as the stock level at the end of time period 0 and we use the notation store_p0 to simplify the formulation of the stock balance constraints:

∀p ∈ PRODS, t ∈ WEEKS: store_pt = store_p,t-1 + produce_pt - DEM_pt

These stock balance constraints state that the quantity store_pt of product that is held in stock at the end of a time period t equals the stock level store_p,t-1 at the end of the preceding period plus the production produce_pt of the time period t minus the demand DEM_pt of this time period.

We wish to have a certain amount of product in stock at the end of the planning period to avoid that stocks run down to zero at the end of the planning horizon. These constraints on the final stock levels are expressed by the constraints:

∀p ∈ PRODS: store_p,NT ≥ FSTOCK_p

We now formulate the various capacity constraints for every time period. The following constraints guarantee that the capacity limits on manpower, machine time, and storage space are kept:

∀t ∈ WEEKS: ∑_{p ∈ PRODS} TIMEW_p · produce_pt ≤ CAPW
∀t ∈ WEEKS: ∑_{p ∈ PRODS} TIMEM_p · produce_pt ≤ CAPM
∀t ∈ WEEKS: ∑_{p ∈ PRODS} SPACE_p · produce_pt ≤ CAPS

The cost function that is to be minimized is the sum of production and storage costs for all products and time periods.

min ∑_{p ∈ PRODS} ∑_{t ∈ WEEKS} ( CPROD_p · produce_pt + CSTORE_p · store_pt )

We obtain the complete mathematical model by the non-negativity constraints for the production variables and for the stored quantities to the constraints described above.

min ∑_{p ∈PRODS} ∑_{t ∈ WEEKS} ( CPROD_p · produce_pt + CSTORE_p · store_pt )
s.t. ∀ p ∈ PRODS, t ∈ WEEKS: store_pt = store_p,t-1 + produce_pt - DEM_pt
∀ p ∈PRODS: store_p,NT ≥ FSTOCK_p
∀ t ∈WEEKS: ∑_{p ∈PRODS} TIMEW_p · produce_pt ≤ CAPW
∀ t ∈WEEKS: ∑_{p ∈PRODS} TIMEM_p · produce_pt ≤ CAPM
∀ t ∈WEEKS: ∑_{p ∈PRODS} SPACE_p ·produce_pt ≤ CAPS
∀ p ∈PRODS, t ∈WEEKS: produce_p,t ≥ 0
∀ p ∈PRODS, t ∈WEEKS: store_p,t ≥ 0

Robust optimization problem

Various assumptions behind the mathematical model that we have stated above might be questioned:

1. Constant resource capacity: availability of personnel most likely will not be constant over time (subject to holidays, training, sick leave etc.) and there is also a risk of scheduled (maintenance) or unscheduled (breakdown) machine outages.
2. Exact demand quantities are known: demand forecasts typically are estimates, most often resulting from an analysis of historical values.

Workers' absence

The case of machine outage (formulated as k contingencies) is studied in Sections Production planning under energy supply uncertainty and Robust unit commitment of this whitepaper. Let us therefore here take a look at how we might capture the uncertainty in the availability of personnel.

Let ABSENCE_t be a maximum limit on the absence hours per time period t (the actual absence will take at most this value), and we also know by experience what is the average absence over a longer period of time (expressed as a percentage A of the total worker hours). We introduce uncertains absent_t to represent the actual absence hours per time period. The worker capacity constraints from the original model are then replaced by the following:

∀ t ∈WEEKS: ∑_{p ∈PRODS} TIMEW_p · produce_pt ≤ CAPW - absent_t
absent ∈ U_absent

where the polyhedral uncertainty set U_absent is characterized by

U_absent = {absent : ∑_{t ∈WEEKS} absent_t ≤ A·CAPW·|WEEKS|,
    0 ≤ absent_t ≤ ABSENCE_t ∀ t ∈WEEKS}

Demand scenarios

For a robust formulation of the demand, assume that we have got a number of different scenarios—obtained from historical data for comparable periods or possibly resulting from different forecasting methodologies—that describe the space of possible realizations of demand. In the place of the fixed demand quantities DEM_pt we now work with uncertain quantities demand_pt that are determined by the demand scenario data SCENDEM_spt for a given set of scenarios s∈SCEN. The demand s included in the original model formulation via the stock balance constraints.

∀p ∈ PRODS, t ∈ WEEKS: store_pt = store_p,t-1 + produce_pt - DEM_pt

A naive 'robustification' might attempt to simply replace the fixed demand quantities by the uncertains demand_pt. However, this approach would not lead to the desired result: by introducing a single uncertain quantity in an equality constraint we do not leave any room for different realizations of the uncertain. We therefore now work with the following two sets of inequalities in the place of the stock balance constraints.

∀p ∈ PRODS, t ∈ WEEKS: store_pt ≤ store_p,t-1 + produce_pt - demand_pt
∀p ∈ PRODS, t ∈ WEEKS: store_pt ≥ store_p,t-1 + produce_pt - max_s∈SCEN SCENDEM_pt

The first of these inequalities states that the demand must be satisfied from the production in a period and the difference between stock levels at the beginning and end of the period, which can be more easily seen in this transformed version of the inequality:

demand_pt ≤ store_p,t-1 + produce_pt - store_pt

The second inequality forces the final stock per period to be at least what remains after satisfying the largest possible demand.

Implementation

The standard deterministic model can be implemented as follows.

model "C-2 Glass production"
 uses "mmxprs"

 declarations
  NT = 12                              ! Number of weeks in planning period
  WEEKS = 1..NT
  PRODS = 1.. 6                        ! Set of products

  CAPW,CAPM: integer                   ! Capacity of workers and machines
  CAPS: integer                        ! Storage capacity
  DEM: array(PRODS,WEEKS) of integer   ! Demand per product and per week
  CPROD: array(PRODS) of integer       ! Production cost per product
  CSTOCK: array(PRODS) of integer      ! Storage cost per product
  ISTOCK: array(PRODS) of integer      ! Initial stock levels
  FSTOCK: array(PRODS) of integer      ! Min. final stock levels
  TIMEW,TIMEM: array(PRODS) of integer ! Worker and machine time per unit
  SPACE: array(PRODS) of integer       ! Storage space required by products

  produce: array(PRODS,WEEKS) of mpvar ! Production of products per week
  store: array(PRODS,WEEKS) of mpvar   ! Amount stored at end of week
 end-declarations

 initializations from 'c2glass.dat'
  CAPW CAPM CAPS DEM CSTOCK CPROD ISTOCK FSTOCK TIMEW TIMEM SPACE
 end-initializations

! Objective: sum of production and storage costs
 Cost:=
  sum(p in PRODS, t in WEEKS) (CPROD(p)*produce(p,t) + CSTOCK(p)*store(p,t))

! Stock balances
 forall(p in PRODS, t in WEEKS)
   Bal(p,t):=
     store(p,t) = if(t>1, store(p,t-1), ISTOCK(p)) + produce(p,t) - DEM(p,t)

! Final stock levels
 forall(p in PRODS) store(p,NT) >= FSTOCK(p)

! Capacity constraints
 forall(t in WEEKS) do
  LimitW(t):= sum(p in PRODS) TIMEW(p)*produce(p,t) <= CAPW     ! Workers
  LimitM(t):= sum(p in PRODS) TIMEM(p)*produce(p,t) <= CAPM     ! Machines
  LimitS(t):= sum(p in PRODS) SPACE(p)*store(p,t)   <= CAPS     ! Storage
 end-do

! Solve the problem
 minimize(Cost)

! Solution printing
 writeln("Total cost: ",getobjval)	
end-model

Workers' absence

For the implementation of the more fine-grained handling of workers' absence we introduce uncertains absent that are bounded by the estimated maximum number of absence hours per time period (ABSENCE) and we equally assume a limit of 5% on the total absence time across the planning period. In the work capacity constraints the absence needs to be deduced from the theoretically available work hours (we here assume that this value is 20% higher than the default limit in the basic model).

declarations
  ABSENCE: array(WEEKS) of real          ! Max. absence (hours)
  absent: array(WEEKS) of uncertain      ! Absence of personnel
 end-declarations

! Limit on total absence (uncertainty set)
 sum(t in WEEKS) absent(t) <= 0.05*CAPW*WEEKS.size
 forall(t in WEEKS) absent(t) <= ABSENCE(t)
 forall(t in WEEKS) absent(t) >= 0

! Uncertains occur in several constraints
 setparam("ROBUST_UNCERTAIN_OVERLAP", true)

! Worker capacity constraints
 forall(t in WEEKS)
   LimitW(t):= sum(p in PRODS) TIMEW(p)*produce(p,t) <= CAPW*1.2 -absent(t)

Demand scenarios

For the formulation of the demand scenarios we need to modify the definition of the constraints that involve demand data, that is, the stock balance constraints. Before stating the scenario constraints, we need to copy the scenario data into the form that is expected by the scenario construct, namely the array SCENDATA that is indexed by the scenario counter and the uncertain demand associated with every time period.

 declarations
  SCEN: range                                      ! Demand scenarios
  SCENDEM: array(SCEN,PRODS,WEEKS) of integer      ! Demand per product & week
  demand: array(PRODS,WEEKS) of uncertain          ! Uncertain demand
  SCENDATA: array(SCEN,set of uncertain) of real   ! Aux. data structure
 end-declarations

! Demand scenarios
 forall(s in SCEN, p in PRODS, t in WEEKS | SCENDEM(s,p,t)>0)
   SCENDATA(s, demand(p,t)):= SCENDEM(s,p,t)
 scenario(SCENDATA)

 ! Stock balances
 forall(p in PRODS, t in WEEKS) do
   Bal(p,t):=
     store(p,t) <= if(t>1, store(p,t-1), ISTOCK(p)) + produce(p,t) - demand(p,t)
   Bal2(p,t):=
     store(p,t) >= if(t>1, store(p,t-1), ISTOCK(p)) + produce(p,t) -
     max(s in SCEN) SCENDEM(s,p,t)
 end-do

! Uncertains occur in several constraints
 setparam("ROBUST_UNCERTAIN_OVERLAP", true)

Both sets of uncertainties can be applied at the same time. However, for the analysis of their effect it might be preferrable to apply only one at a time.

Results

The original problem description and instance data are taken from [GHP02] (Section 8.2 Production of drinking glasses). The costs and resource usage data for the six glass types are listed in Table Data for six glass types.

Table 2: Data for six glass types

	Production cost	Storage cost	Initial stock	Final stock	Timeworker	Timemachine	Storage space
V1	100	25	50	10	3	2	4
V2	80	28	20	10	3	1	5
V3	110	25	0	10	3	4	5
V4	90	27	15	10	2	8	6
V5	200	10	0	10	4	11	4
V6	140	20	10	10	4	9	9

The solution of the original problem with the basic demand scenario has a total cost of € 185,899. The resulting detailed production plan is displayed in Table Optimal production plan for basic demand scenario. We find that the available manpower is fully used most of the time (in the first week, 351 hours are worked, in all other weeks the limit of 390 hours is reached) and the machines are used to their full capacity in certain time periods (weeks 1-3 and 5), but the available storage space is in excess of the actual needs.

Table 3: Optimal production plan for basic demand scenario

	Week	1	2	3	4	5	6	7	8	9	10	11	12
V1	Prod.	8.8	5.5	0.6	30.2	27.4	8.6	23	20	29	30	28	42
	Store	38.8	22.2	4.8	-	10.4	–	–	–	–	–	–	10
V2	Prod.	0	16	23	20	11	10	12	34	21	23	30	22
	Store	3	–	–	–	–	–	–	–	–	–	–	10
V3	Prod.	18	35	17	10	9	21	23	15	10	0	13	27
	Store	–	–	–	–	–	–	–	–	–	–	–	10
V4	Prod.	16	45	24	38	41	20	19	37	28	12	30	47
	Store	–	–	–	–	–	–	–	–	–	–	–	10
V5	Prod.	47.7	14.6	35.1	14.3	23.5	22.8	43.8	0	26.5	2.8	0	0
	Store	24.7	19.3	31.4	30.8	44.2	45	70.8	40.75	39.25	35	20	10
V6	Prod.	12	18	20	19	18	35	0.8	27.2	12	49	29.2	5.8
	Store	–	–	–	–	–	–	0.75	–	–	19	27.25	10
Workers		351	390	390	390	390	390	390	390	390	390	390	390
Machines		850	850	850	753.2	850	836.8	790	675.2	742.5	650.2	641.2	641.8
Space		268.8	166.2	144.8	123	218.4	180	289.8	163	157	311	325.2	330

If we try to introduce robustness to such a tightly constrained problem, the outcome most likely will be 'problem infeasible' as there is no slack to incorporate alternatives. We have therefore somewhat relaxed the original bound on the personnel hours, assuming that its original value represents a rough worst-case estimate and that the actually available working hours are 20% higher. The more fine-grained estimate of absence results in the solution summarized in Table Summary results with robust formulation of absence. The overall cost of € 181,210 is slightly lower than the previous, fixed worst-case absence case.

Table 4: Summary results with robust formulation of absence

	Week	1	2	3	4	5	6	7	8	9	10	11	12
Workers		243	378	370	407	325	398	383	414	412	445	429	437
	CAPW-ABSENCE	437	437	429	429	414	398	398	414	445	445	429	437
Machines		609	850	736	770	736	794	772.2	739.8	803	839.5	734	747.5
Space		152.5	32	0	0	20	0	99	0	16	130	219.5	330

The scenario-based approach results in a higher total cost of €203,545. In the summary results in Table Summary results with demand scenarios we observe that both, machine capacity and workers' hours, are most of the time used at or close to their capacity limit (850 and 429=1.1·390 respectively). Furthermore, larger quantities of products are held in stock.

Table 5: Summary results with demand scenarios

	Week	1	2	3	4	5	6	7	8	9	10	11	12
Workers		363	425	425	425	425	425	425	425	425	425	425	425
Machines		850	850	850	850	850	850	850	850	850	786.7	711	700.3
Space		230.7	145.9	150.4	126.3	233.2	211.9	306.8	181.7	169.7	256.7	305.7	330

For easier comparison, Table Summary results for deterministic model with 1.1CAPW shows the summary results for the original model with the same capacity limits as have been used wit the robust formulation in Table Summary results with demand scenarios, the total cost is in this case €181,432.

Table 6: Summary results for deterministic model with 1.1·CAPW

	Week	1	2	3	4	5	6	7	8	9	10	11	12
Workers		243	378	370	407	305	418	393	425	425	425	425	425
Machines		609	850	736	770	681	849	799	771.2	840	783.2	721	721.5
Space		152.5	32	0	0	0	0	108.7	21.2	50.6	151.5	245.5	330