IEEE/CAA Journal of Automatica Sinica  2015, Vol.2 Issue (2): 217-225   PDF    
Production Line Capacity Planning Concerning Uncertain Demands for a Class of Manufacturing Systems with Multiple Products
Hao Liu, Qianchuan Zhao , Ningjian Huang, Xiang Zhao    
1. Center for Intelligent and Networked Systems(CFINS), Department of Automation, TNList Lab, Tsinghua University, Beijing 100084, China;
2. Research and Development Center, Institute of Space System Engineering, China Academy of Space Technology, Beijing 100094, China;
3. Global Research and Development Center, General Motors Company, Warren, MI 48090, USA
Abstract: In this paper, we study a class of manufacturing systems which consist of multiple plants and each of the plants has capability of producing multiple distinct products. The production lines of a certain plant may switch between producing different kinds of products in a time-sharing mode. We optimize the capacity configuration of such a system's production lines with the objective to maximize the overall profit in the capacity planning horizon. Uncertain demand is incorporated in the model to achieve a robust configuration solution. The optimization problem is formulated as a nonlinear polynomial stochastic programming problem, which is difficult to be efficiently solved due to demand uncertainties and large search space. We show the NP-hardness of the problem first, and then apply ordinal optimization (OO) method to search for good enough designs with high probability. At lower level, an mixed integer programming (MIP) solving tool is employed to evaluate the performance of a design under given demand profile.
Key words: Capacity planning     uncertain demands     ordinal optimization (OO)    
Ⅰ. INTRODUCTION

Mass customization has been recognized as one of the new paradigms for today$'$s automotive manufacturing. As auto companies increase their manufacturing flexibility,a vehicle assembly plant usually possesses capability of producing multiple distinct vehicle models in order to meet rapidly changing market and gain competitive advantages. As a result of such a paradigm change,automotive companies having a global manufacturing network need urgently a planning tool that helps to allocate production/assembly lines into multiple plants and to find an optimal solution of line capacity configuration to meet the uncertain market demands. Such decisions are believed to influence the performance of a manufacturing network and thus the company$'$s competitiveness[1].

Motivated by practical backgrounds,this paper is exploring ways to meet these challenges. We studied a class of manufacturing systems,of which the features will be described and modeled in detail in Section Ⅲ. We tried to address the problem of optimizing the capacity configuration of the production lines in the system,with the objective to maximize the overall profit in the capacity planning horizon (often several years). Incorporating the future uncertain demand,the problem is formulated into a two-stage stochastic nonlinear programming problem with the first stage comprising capacity configuration decisions and the second stage with production decisions. The solution of the capacity configuration will eventually determine the company$'$s investment on its production lines.

The class of manufacturing systems studied in this paper is modeled mainly based on our practical investigation. In current literature,limited study is found that investigates a manufacturing system like the class we study here. Similar studies on planning production lines$'$ capacity for manufacturing systems exist in literature but such studies focus on various systems featuring in different characteristics. The most similar study, for example,is planning strategic multi-site and multi-product production networks. Reference [1] reported the BMW$'$s global production network and its planning with investment,production and supply chain optimization incorporated. Reference [2] planned the strategic network for an international automotive manufacturer,focusing on the decisions of allocating products to different plants and expanding the capacity of a given manufacturing network with fixed plant locations. Reference [3] also modeled and optimized the production planning in the automotive industry under uncertain demands,including tactical aspects such as workforce planning. References [4] and [5] are other two recent examples. However,the system studied in this paper has some features that are not considered in the above literature,and thus is differently modeled and solved. The features are described at the beginning of Section Ⅲ.

For two-stage stochastic programming,techniques such as Bender$'$s decomposition (as in [3] and [6]) or tools such as Lingo (as in [7]) could be applied. Although these are relatively efficient ways and are possible to be further accelerated,the computation burden would still be too large to handle within limited time if the problem is of a large scale or if the solution performance estimation is time-consuming. To address this,a solution framework will be proposed in this paper applying ordinal optimization (OO)[8] to find good enough solutions with high probability. The details of the framework will be given in Section Ⅲ-C.

The rest of the paper is organized as follows. In Section Ⅲ,we will introduce the related concepts of the manufacturing system we investigated and then give a general formulation of the problem. In Section Ⅲ,we will analyze the problem and find ways to solve it. In Section Ⅳ,numerical results will be presented. Section Ⅴ concludes the paper.

Ⅱ. THE PLANNING PROBLEM: A GENERAL MODEL

We propose in this section a general model of the production line capacity planning problem of a class of manufacturing system. The class of manufacturing system we considered here has a basic feature that the system consists of multiple plants (usually located at different places geographically) and each of the plants has capability of producing multiple distinct products. Some of the products and their production processes are similar,and their production processes are similar,and the production lines could switch between producing any kind of them only with minor modifications of the equipment,tooling or the equipment configurations. However,the modifications are not dramatic to produce totally different products. Fig. 1 gives a schematic example of such a manufacturing system. In the example,products A and B are similar,but product C is not. Plants 1 and 2 have production lines capable of producing both products A and B. Plant 1 also has production lines capable of producing product C. Plant 3 only has production lines capable of producing product C.

Download:
Fig. 1. Schematic example of the class of manufacturing system considered in this paper.

A typical example of such a manufacturing system is one that consists of several vehicle assembly plants of an auto manufacturing company. Those assembly plants may be located at different places and could individually produce different models of vehicles. A production line of a vehicle assembly plant usually consists of two parallel sub-lines--vehicle assembly sub-line makes the body; powertrain assembly sub-line makes the chassis; the body and chassis are finally assembled together to produce a vehicle. The lines can be shared by the assembly of different vehicle models. A plant could choose to produce some models of vehicles according to its geographical characteristics,product strategies,and forecasted global or regional market demands for specific vehicle models,etc.

A. Related Concepts of the Manufacturing System

Uncertainty

When addressing the production line capacity planning problem for a manufacturing system,we face many respects of uncertainty such as the market demand,states of the machines (working or failure),raw material prices and product prices. In this paper,we only consider the uncertainty of the market demand,since this is always the most fundamental and challenging uncertainty at a planning stage. In the planning stage,we can always assume plants have similar reliability in a statistical manner. By this assumption the modeling could be simplified but without sacrificing the essential insights one could gain from planning.

Market demand forecasting is necessary for production capacity planning. This could be done by first analyzing the historical sale data to gain some knowledge about the demand trends or distribution, and then forecasting based on the knowledge. Proper statistical techniques could be used for both analyzing and forecasting. Although the knowledge gained is important as a guide to forecast the future demand and facilitate reasonable planning,the demand in the past is hardly repeated in the future due to the inevitable uncertainty existing in the market. Therefore we have to take into account the randomness in addition to the basic knowledge to make the planning more robust.

Production rates of a plant

The production rate of a production line is defined as the number of products produced by the line in per unit time. Here,we do not focus on any individual production line but a whole plant. When we talk about the line production rate of a plant,we see the production lines of the plant as a whole and consider their overall production rate,i.e.,the capacity of a plant is the sum of production rates of all products in this plant.

As mentioned before,the production lines of a plant may be used to produce different products. When considered as a whole,the production lines may have different production rate respectively for different products. There are mainly two reasons. One is that the process requirements of different products are different. The other is that the product-specific equipment installed for different products varies. When the process requirement of a certain product is fixed,the plant has to install more product-specific equipment if there is a requirement from the plant to increase the production rate of a specific product.

The amount of product-specific equipment installed for different products in a plant in fact determine the plant$'$s respective maximum production rates for the products. Actually,this is what we need to decide before the production starts. In the optimization problem proposed in Section Ⅲ,the maximum production rates are modeled as the key decision variables.

For a certain product,some equipment may not be running when the forecasted product demand is low. Thus,the respective actual production rates for different products may vary from time to time according to the production plan.

Production period

In our model,we use week as a unit time period. The period is defined for the convenience of demand forecasting and production rate adjustment. First,we assume the demand forecasting gives the demand of different products for every week of the planning horizon. Second,we assume the plants could adjust their actual production rates for the products according to the forecasted demand at the beginning of every week and maintain the rates unchanged for the whole week.

Shift pattern,normal working time and overtime

The shift pattern adopted by a plant in a production period (week in our model) determines the plant$'$s total working time available in that period. A plant can adopt different shift patterns in different periods to achieve different levels of total working time. The total working time includes two parts: normal working time and overtime. For instance,the workers could be divided into three crews,and are arranged for work in 3 shifts per day,each crew works in a shift for 8 hours. Each worker works normally for 5 days per week. Then the total normal working time in a week is 8 hrs/shift$\times$3 shifts/day$\times$5 days=120hrs. If the plant is needed to produce more in some week,an overtime day could be arranged. In this case,the overtime hours is 8 hrs/shift $\times$ 3 shifts/day $\times$1 days= 24hrs and the total working time available in the week is 120 hrs + 24 hrs = 144 hrs. The overtime is an important flexibility that a plant could utilize to achieve a high production volume when needed.

In our model,we assume for simplicity that the plants respectively adopt a fixed shift pattern. Therefore,the total working time of the plants and the normal working time and overtime in each period are all deterministic.

Line sharing production

For a plant that could produce more than one kind of products,the production of the products will share the production lines of the plant. In our model,we assume the time allotment is discrete,for example,in unit of hours.

Plant capacity.The capacity of a plant in a period could be defined by combining the plant$'$s line production rates for different products and its total working time available. For example,if a plant could produce product A and product B with respective production rates 60 products/hr and 40 products/hr,and its total working time in a week is 120 hrs,and then the plant$'$s weekly capacity is $60 \times 120 = 7 200$ product A or $40 \times 120 = 4 800$ product B,the same could be represented by Fig. 2.

Download:
Fig. 2. Schematic diagram of plant capacity.

Since the time allotment occurs when actual production starts,the capacity planning is confined to the decision on maximum production rates configuration.

Cost profile

We consider three aspects of costs in our model:

1) Investment cost: the cost of investment on production lines. The investment cost on the production line equipment for a product in a plant is a piecewise linear function of the corresponding maximum production rate of the product in the plant (Fig. 3).

Download:
Fig. 3. The relationship of investment cost and the maximum production rate. Note here a left-continuous function is adopted just for illustration. Our method also works for right-continuous cost functions.

2) Set-up cost: the cost of setting up the equipment for production,including the cost of facilities installing,tooling exchange,line maintenance,etc. The set-up cost of producing a product in a plant in a period is positively correlated to the actual production rate of the product in the plant in that period. In our model,we assume the set-up cost is proportional to the actual production rate.

3) Production cost,which includes two parts:

a) Consumption cost. the cost of material and energy consumption, wear and tear of facility and equipment,etc.,which is proportional to the production.

b) Labor cost. the cost of labor. The labor cost is also proportional to the production but the proportionality coefficients are different for the production in normal working time and in overtime. Usually the former is lower than the later due to the extra payment to workers who are working overtime (Fig. 4).

Download:
Fig. 4. The relationship of labor cost and production.

Overproduction and underproduction

We assume in our model no inventory and thus no overproduction. However,underproduction is allowed but will cause a penalty. As we consider the underproduction happening more seriously in the near term than that in the future,a discount factor of penalty is introduced.

B. Problem Formulation

Our model aims at finding a proper design of the maximum production rates of different products for the plants at the beginning of a planning horizon. After the design is decided,the actual production in the plants cannot exceed the plants' respective maximum production rates. However,as mentioned above,the plants can adjust their actual production rates and the time allotment for different products periodically according to the forecasted demand. Thus, there are two stages of decisions in our problem. The first stage decision is to decide the maximum production rates. The second stage decision,which is to be made relying on the first stage decision, is to decide the actual production plan.

Considering the demand uncertainty,the capacity planning problem is formulated as a stochastic programming problem as follows.

Given values

$i \in I$: index of a plant. $I$ = {1,2,$\cdots$,number of plants}.

$j \in J$: index of a product. $J$ = {1,2,$\cdots$,number of products}.

$t \in T$: index of a period. $T$ = {1,2,$\cdots$,number of periods}.

$HIW_{it}^n$ ($HIW_{it}^o$,respectively): available normal working hours (overtime hours,respectively) of plant $i$ in period $t$. HIW stands for ``hours In a week'',as we consider periods as weeks.

$IC_{ij}$($\cdot$): investment cost of the production equipment of product $j$ in plant $i$,which is a stepwise function of $JPH_{ij0}$ (to be introduced later).

$sc_{ijt}$: set-up cost coefficient of setting up the production equipment for product $j$ in plant $i$ in period $t$,which multiplied by $JPH_{ijt}$ (to be introduced later) makes the set-up cost. If the product $j$ is not being produced at plant $i$ in period $t$,then $sc_{ijt}$ equals to 0.

$cc_{ijt}$: consumption cost per product $j$ produced in plant $i$ in period $t$.

$lc_{ijt}^n$ ($lc_{ijt}^o$,respectively): labor cost per product $j$ produced in plant $i$ in period $t$ in normal working hours (overtime hours,respectively).

$p_j$: coefficient of penalty for underproduction of product $j$.

$\alpha$: discount factor of penalty for underproduction.

$w_{jt}$: selling price per product $j$ in period $t$.

$d_{jt}$: demand for product $j$ in period $t$ (random variable). The vector of the demands will be denoted by ${\pmb d}$.

Decision variables

First stage decision variables:

$JPH_{ij0}$: maximum production rate of product $j$ in plant $i$. JPH stands for "job per hour". If plant $i$ does not produce product $j$,then $JPH_{ij0}$ = 0.

The vector of the first stage decision variables will be denoted by ${\pmb{JPH_0}}$. A solution of ${\pmb{JPH_0}}$ will also be called a "design" hereinafter.

Second stage decision variables:

$JPH_{ijt}$: actual production line rate of product $j$ in plant $i$ in period $t$.

$y_{ijt}^n$ ($y_{ijt}^o$,respectively): normal working hours (overtime hours,respectively) allotted to product $j$ in plant $i$ in period $t$.

The vector of the second stage decision variables will be denoted by ${\pmb x}$.

Objective function

For clarity,we write the following expressions before giving the objective function and constraints:

Investment cost:

\begin{align} IC = \sum\limits_{i \in I,j \in J} {I{C_{ij}}(JP{H_{ij0}})}. \end{align} (1)

Production cost:

\begin{align} \begin{aligned} PC & = \sum\limits_{i \in I,j \in J,t \in T} \left[ sc_{ijt}JPH_{ijt} + \left( {cc_{ijt} + lc_{ijt}^n} \right){y_{ijt}^n}{JPH_{ijt}}\right.\\ & \left. +\left( {cc_{ijt} + lc_{ijt}^o} \right){y_{ijt}^o}{JPH_{ijt}} \right] \end{aligned} \end{align} (2)

Total penalty of underproduction:

\begin{align} PU = \sum\limits_{j \in J} {\left[{{p_j}\sum\limits_{t \in T} {{\alpha ^{t - 1}}\left( {{d_{jt}} - \sum\limits_{i \in I} {\left( {y_{ijt}^n + y_{ijt}^o}\right)JP{H_{ijt}} } } \right)} } \right]}. \end{align} (3)

Total revenue:

\begin{align} R = \sum\limits_{i \in I,{\rm{ }}j \in J,{\rm{ }}t \in T} {(y_{ijt}^n + y_{ijt}^o)JP{H_{ijt}}{w_{jt}}}. \end{align} (4)

The total expense,denoted by $E$,is considered as the total cost plus the penalty,that is

\begin{align} E = IC + PC + PU, \end{align} (5)

and the profit is

\begin{align} R - E. \end{align} (6)

After combining the similar terms in ($R-E$),we have

\begin{align} \begin{aligned} R - E & = \sum\limits_{i \in I,j \in J,t \in T} {\left( {r_{ijt}^ny_{ijt}^nJP{H_{ijt}} + r_{ijt}^oy_{ijt}^oJP{H_{ijt}}} \right)} {\rm{ }} -\\ & \sum\limits_{i \in I,j \in J,t \in T} {s{c_{ijt}}JP{H_{ijt}}} - \sum\limits_{i \in I,j \in J} {I{C_{ij}}(JP{H_{ij0}})}-\\ & \sum\limits_{j \in J,t \in T} {{p_j}{\alpha ^{t - 1}}{d_{jt}}}, \end{aligned} \end{align} (7)

where

\begin{align} r_{ijt}^n = {p_j}{\alpha ^{t - 1}} + {w_{jt}} - c{c_{ijt}} - lc_{ijt}^n, \end{align} (8)
\begin{align} r_{ijt}^o = {p_j}{\alpha ^{t - 1}} + {w_{jt}} - c{c_{ijt}} - lc_{ijt}^o. \end{align} (9)

Let

\begin{align} &f({\pmb{JPH_0}}) = - \sum\limits_{i \in I,j \in J} {I{C_{ij}}(JP{H_{ij0}})},\\ \end{align} (10)
\begin{align} &\begin{aligned} g({\pmb x}) & = \sum\limits_{i \in I,j \in J,t \in T} {\left( {r_{ijt}^ny_{ijt}^nJP{H_{ijt}} + r_{ijt}^oy_{ijt}^oJP{H_{ijt}}} \right)} - \\ & \sum\limits_{i \in I,j \in J,t \in T} {s{c_{ijt}}JP{H_{ijt}}}. \end{aligned} \end{align} (11)

To maximize the profit,we could write the objective function as

\begin{align} \max f({\pmb{JPH_0}}) + g({\pmb x}) - \sum\limits_{j \in J,t \in T} {{p_j}{\alpha ^{t - 1}}{d_{jt}}}. \end{align} (12)

Constraints

Constraints on the first stage decision variables:

\begin{align} {\pmb{JPH_0}} \ge {\bf 0}, \end{align} (13)

that is,the maximum production rates cannot be negative.

Constraints on the second stage variables are:

\begin{align} &JP{H_{ijt}} \le JP{H_{ij0}},\forall i \in I,j \in J,t \in T,\\ \end{align} (14)
\begin{align} &\sum\limits_{j \in J} {y_{ijt}^n} \le HIW_{it}^n,\forall i \in I,t \in T,\\ \end{align} (15)
\begin{align} &\sum\limits_{j \in J} {y_{ijt}^o} \le HIW_{it}^o,\forall i \in I,t \in T,\\ \end{align} (16)
\begin{align} &\sum\limits_{i \in I} {\left( {y_{ijt}^nJP{H_{ijt}} + y_{ijt}^oJP{H_{ijt}}} \right)} \le {d_{jt}},\forall j \in J,t \in T,\\ \end{align} (17)
\begin{align} &JP{H_{ijt}} \ge 0,y_{ijt}^n,y_{ijt}^o \in {\bf N},\forall i \in I,j \in J,t \in T, \end{align} (18)

where:

1) Constraint (14) sets upper bounds on the actual production rates (to not let exceed the maximum production rates);

2) Constraint (15) ((16),respectively) indicates that in any plant and in any period,the summation of the normal working time (overtime,respectively) of producing all the possible products cannot exceed the available total normal working time (total overtime,respectively) determined by the shift pattern adopted;

3) Constraint (17) indicates that no overproduction is permitted for any product in any period;

4) Constraint (18) indicates that the working time is discretely allotted to different products (unit of hours assumed).

For clarity,we denote constraints (14) $\sim$ (17) by ${\pmb h}({\pmb x},{\pmb{JPH_0}},{\pmb d}) \le {\bf 0}$,and constraint (18) by ${\pmb x} \in {\pmb X}$ in the following. By these denotations the formulation could be written as

\begin{align} {\max _{{\pmb{JPH_0}}\ge {\bf 0}}}f({\pmb{JPH_0}}) + g({\pmb x}) - \sum\limits_{j \in J,t \in T} {{p_j}{\alpha ^{t - 1}}{d_{jt}}} , \end{align} (19)

s.t.

\begin{align} {\pmb h}({\pmb x},{\pmb{JPH_0}},{\pmb d}) \le {\bf 0},{\pmb x} \in {\pmb X}. \end{align} (20)

This problem could not be directly solved due to the uncertainty caused by the uncertain demand ${\pmb d}$. Practically,for such a stochastic problem,we usually expect to find a solution of ${\pmb{JPH_0}}$ that is ``averagely'' optimal,that is,optimal in the sense of performance expectation with respect to the uncertain ${\pmb d}$. Hence,the objective function could be written as

\begin{align} {\max _{{\pmb{JPH_0}} \ge {\bf 0}}}{E_{\pmb d}}\left[f({\pmb{JPH_0}}) + g({\pmb x}) - \sum\limits_{j \in J,t \in T} {{p_j}{\alpha ^{t - 1}}{d_{jt}}} \right], \end{align} (21)

and could be further simplified to

\begin{align} {\max _{{\pmb{JPH_0}} \ge {\bf 0}}}f({\pmb{JPH_0}}) + {E_{\pmb d}}\left[g({\pmb x}) \right], \end{align} (22)

since the last term of the former is actually a constant with the distribution of ${\pmb d}$ being known and thus has no effect on the final solution and can be omitted.

For the convenience of problem analysis,we equivalently write the above formulation following the notation conventions of [9] as P1:

\begin{align} {\max _{{\pmb{JPH_0}} \ge {\bf 0}}}f({\pmb{JPH_0}}) + {\pmb Q}({\pmb{JPH_0}}) \end{align} (23)

where

\begin{align} {\pmb Q}({\pmb{JPH_0}}) = {E_{\pmb d}}\left[{{\pmb Q}({\pmb{JPH_0}},{\pmb d})} \right] \end{align} (24)

and ${\pmb Q}({\pmb{JPH_0}},{\pmb d})$ is defined as the second stage problem P2:

\begin{align} {\pmb Q}({\pmb{JPH_0}},{\pmb d}) = \mathop {\max }\limits_{\pmb x} \left\{ {\left. {g({\pmb x})} \right|{\pmb h}({\pmb x},{\pmb{JPH_0}},{d}) \le 0,{\pmb x} \in {\pmb X}} \right\}, \end{align} (25)

which is a deterministic programming problem trying to find an optimal second stage solution with both ${\pmb{JPH_0}}$ and ${\pmb d}$ being given.

Ⅲ. PROBLEM ANALYSIS AND SOLUTION A. Problem Complexity

To explore the complexity of P1,we first analyze the complexity of the second stage problem P2. The polynomial terms in the objective function $g({\pmb x})$ and the constraints ${\pmb h}({\pmb x},{\pmb{JPH_0}},{\pmb d}) \le {\bf 0}$ makes P2 possess no convexity and hard to be globally optimized. Furthermore,the discreteness in the normal and overtime working hours cause significant complexity in the problem. Consider a simple case of P2, which involves one plant,several products,one period,and no overtime. The number of working hours allotted to each product is constrained to be either 0 or a certain positive integer. In this case,P2 could be explicitly written as P3 (with unnecessary subscripts of plant and period omitted)

\begin{align} \max \sum\limits_{j \in J} {{r_j^n}{y_j^n}{JP{H_j}}} - \sum\limits_{j \in J} {s{c_j}JP{H_j}}, \end{align} (26)

s.t.

\begin{align} &JP{H_j} \le JP{H_{j0}},\forall j \in J,\\ \end{align} (27)
\begin{align} &\sum\limits_{j \in J} {y_j^n} \le HIW^n,\\ \end{align} (28)
\begin{align} &{y_j^n}{JP{H_j}} \le {d_j},\forall j \in J,\\ \end{align} (29)
\begin{align} &JP{H_j} \ge 0,y_j^n \in \{ 0,{Y_j}\} \forall j \in J, \end{align} (30)

where $Y_j$ is a constant positive integer not larger than $HIW^n$ (for any $j$). We now prove P3 is NP-hard.

Proposition 1. P3 is NP-hard.

Proof. set $JP{H_{j0}} = {d_j}/HI{W^n}$ for any $j \in J$,which together with constraints (27) and (28) imply that ${y_j^n}{JP{H_j}} \le {d_j}$,and then constraint (29) could be omitted. Furthermore,for any $j \in J$,set $sc_j = 0$ and $r_j^n = {Z_j} \cdot JP{H_{j0}}/{Y_j}$,where $Z_j$ is a constant positive integer. Since for any $j$,$r_j^n \ge 0$,therefore the optimal solution should satisfy $JPH_j$ equals to $JPH_{j0}$,and then constraint (27) could be omitted. After removal of the above restriction,we obtain a special case of problem P3 as problem P4

\begin{align} \max \sum\limits_{j \in J} {{{Z_j} \cdot \frac{y_j^n}{Y_j}}}, \end{align} (31)

s.t.

\begin{align} &\sum\limits_{j \in J} {y_j^n} \le HIW^n,\\ &y_j^n \in \{ 0,{Y_j}\},\forall j \in J. \end{align} (32)
\begin{align} &y_j^n \in \{ 0,{Y_j}\},\forall j \in J. \end{align} (33)

The decision version of P4 is actually a knapsack problem. Thus we know P4 is NP-hard,and so is P3.

The whole problem P1 possesses some challenges other than the NP-hardness arising from the second stage problem P2. First,for a given ${\pmb{JPH_0}}$,the uncertain demand ${\pmb d}$ makes the objective value $f({\pmb{JPH_0}}) + {\pmb Q}({\pmb{JPH_0}})$ impossible to be accurately estimated. In fact,we could only estimate the expectation term ${\pmb Q}({\pmb{JPH_0}})$ based on demand samples. That is,for a given ${\pmb{JPH_0}}$,we generate some demand samples,solve the corresponding second stage problems with the demand samples respectively substituted for the demand variables,and then average the optimal objective values to obtain ${\pmb Q}({\pmb{JPH_0}})$. Obviously,the more demand samples we use,the higher the estimation confidence level we would obtain,but the computation burden will correspondingly increase.

Second,the size of search space of solutions will significantly increase as the size of the problem increases. Consider the case that ${JPH}_{ij0}$ could be chosen from a finite set with $M$ candidates for any $i$ and any $j$. Then the total number of possible ${\pmb{JPH_0}}$ is ${M^{I \times J}}$,where $I$ and $J$ denote the number of plants and number of products,respectively. We could see that the size of search space will increase exponentially with the size of the problem.

B. Solving the Second Stage Problem P2

For polynomial programming problems,there are several global optimal solution algorithms that could be found in literature. The common technique used in these algorithms is first replacing the product terms with additional variables to obtain a relaxed problem and then introducing additional reasonable constraints that help to find the optimal solution. One example of such algorithms is the reformulation-linearization/convexification technique (RLT) proposed in [10],being used together with branch-and-bound technique. However,RLT may not find the optimal solution within finite steps of branch-and-bound. Another example is to convert the polynomial programming problems to 0-1 linear programming problems if the original problem possesses some special features[11]. After conversion,the problem could be solved using the developed solving tools.

In our work,we converted our second stage problem to a mixed integer programming (MIP) problem by applying the conversion method proposed in [11] but with minor modification. We will first introduce the converting technique first and then explain the modification in the following.

Reference [11] gives an approach of converting a 0-1 polynomial programming problem to a 0-1 linear programming problem. The key idea of the approach is first replacing each product term with an additional variable,and then introducing additional constraints correspondingly for each replacement such that the value of the additional variable equals to the value of the corresponding product term in any case. In this way,the two problems before and after the replacement are kept equivalent. Noting that all the polynomial terms in our problem only involve two variables,we demonstrate the approach for this case for brevity. For a polynomial programming program involving a product term $ u \cdot v$ ($u$,$v$ $ \in \{0, 1\}$ assumed),we can substitute an additional variable $W$ for $ u \cdot v$,and then introduce four additional constraints as $ u + v - W \le 1$,$u \ge W$,$v \ge W$ and $W \in \{0,1\}$. The constraints result in $W = 1$ only when both $u$ and $v$ equal to 1 and $W = 0$ otherwise. Thus we know the two problems before and after the substitution are equivalent.

Actually,the assumption $u,v \in \{0,1\}$ could be relaxed to $u \in \{0,1\}$ and $v \in [0,1]$,only requiring the constraint $W \in \{0,1\}$ being changed to $W \in [0,1]$ to maintain the equivalence. In this case,the constraints result in $W = v$ when $u = 1$ and $W = 0$ when $u = 0$.

In our second stage problem,all the product terms involve two variables,of which one is a positive integer ($y_{ijt}^n$ or $y_{ijt}^o$) and the other is a bounded continuous positive number ($JPH_{ijt}$). To apply the conversion method of [11] with the above generalization,we introduce the following substitution for any $i$,$j$ and $t$ to make the problem contain only 0-1 integer variables and continuous variables belong to [0, 1]:

\begin{align} &y_{ijt}^n = {2^{K - 1}}y_{ijt,K}^n + {2^{K - 2}}y_{ijt,K - 1}^n + \cdots + y_{ijt,1}^n ,\notag\\ &\qquad K = \min \left\{ {x \in {{\bf N}_ + }\left| {{2^x} > HIW_{it}^n} \right.} \right\},\\ \end{align} (34)
\begin{align} &y_{ijt}^o = {2^{L - 1}}y_{ijt,L}^o + {2^{L - 2}}y_{ijt,L - 1}^o + \cdots + y_{ijt,1}^o,\notag\\ &\qquad L = \min \left\{ {x \in {{\bf N}_ + }\left| {{2^x} > HIW_{it}^o} \right.} \right\},\\ \end{align} (35)
\begin{align} &JP{H_{ijt}} = JP{H_{ij0}}{z_{ijt}}, \end{align} (36)

where $y_{ijt,k}^n,y_{ijt,l}^o \in \{ 0,1\} (k = 1,\cdots ,K,l = 1,\cdots ,L)$ and ${z_{ijt}} \in [0,1]$. The substitution and conversion result in a mixed integer programming (MIP) problem,for which we could apply any MIP solving tool,for example,the solving tool provided by IBM ILOG CPLEX[12].

C. Solving the Whole Problem P1

As discussed above,there are three main challenges to solve P1 to obtain optimal first stage decisions: the NP-hardness of the second stage problem,the uncertainty of the demand and the large search space of solutions. The former two challenges determine that we could not exactly and efficiently estimate the performance for a given first stage decision solution. The third challenge means we have to explore a lot of candidate solutions for optimization. To meet these challenges,we turn to ordinal optimization (OO) method[8],which tries to find good enough designs with a high probability instead of finding the optimal design for sure. OO saves computation burden by using a rough model to estimate the performance of a given design and investigate only a limited number of candidate solution sampled from the original large search space.

The OO applied solution framework for problem P1 is as follows:

Step 1. Sampling.

Randomly and uniformly sample $N$ (say 1 000) designs of maximal production rates configuration (${\pmb{JPH_0}}$).

Step 2. Performance Estimation (crude estimation).

(1) Randomly generate $n_1$ (a small number,say 1 or 2) of demand instances;

(2) For each of the $N$ design samples,calculate the corresponding profits under each demand instance by solving the corresponding second stage problems,and then average the profits to obtain a rough estimation of the sample$'$s performance;

(3) Estimate the ordered performance curve (OPC) type based on the sorted performances of the $N$ designs.

Step 3. Selecting designs (horse racing rule used here).

Order the estimated performances of the designs and select the top $s$ designs as the selected set,where $s$ is determined according to a universal alignment probability (UAP) table and desired good enough level $k$. High noise level could be assumed since no prior knowledge is known about the noise. It should be noted that the UAP adopted should conform to the required confidence level,i.e., the probability of guaranteeing to find a satisfactory solution later.

Step 4. Further distinguishing (more accurate performance estimation).

(1) Randomly generate $n_2$ (a relatively large number,say 10) instances of demand;

(2) Repeat the performance estimation Step 2(2) with the demand instances generated in Step4(1) to obtain more accurate estimation of the selected samples$'$ performances;

(3) Select the design with the best average performance as the final solution.

Ⅳ. NUMERICAL RESULTS A. A Numerical Example of the Second Stage Problem

To demonstrate the feasibility of the solution method of the second stage problem discussed in Section Ⅲ-B,we here considered a simple example of a second stage problem,which involves 2 plants,3 products and 1 period. ${\pmb{JPH_0}}$ and ${\pmb d}$ are given as

\begin{align} &{\pmb{JPH_0}} =\left( {JP{H_{ij0}}} \right) = \left[ {\begin{array}{*{20}{c}} 0&{50}&{50}\\ {50}&{50}&0 \end{array}} \right],\\\end{align} (37)
\begin{align} &{\pmb d} = \left( {{d_j}} \right) = \left[{\begin{array}{*{20}{c}} {5 000}&{5 000}&{5 000} \end{array}} \right]. \end{align} (38)

The normal working hours and overtime hours are respectively given as

\begin{align} \left( {HIW_i^n} \right) = \left[{\begin{array}{*{20}{c}} {120}&{120} \end{array}} \right],\left( {HIW_i^o} \right) = \left[{\begin{array}{*{20}{c}} {24}&{24} \end{array}} \right]. \end{align} (39)

Other coefficients are set such that the rewards of producing per unit of products 1 and 2 are the same,and are higher than that of producing per unit of product 3. After applying the substitution and conversion introduced in Section Ⅲ-B,the resulting problem could be solved by ILOG CPLEX and an optimal solution could be obtained as:

actual production rates:

\begin{align} \left( {JPH_{ij}} \right) = \left[{\begin{array}{*{20}{c}} 0&{41.67}&0\\ {34.72}&0&0 \end{array}} \right], \end{align} (40)

and normal working and overtime hours distribution results:

\begin{align} \left( {y_{ij}^n} \right) = \left[{\begin{array}{*{20}{c}} 0&{120}&0\\ {120}&0&0 \end{array}} \right],\left( {y_{ij}^o} \right) = \left[{\begin{array}{*{20}{c}} 0&0&0\\ {24}&0&0 \end{array}} \right]. \end{align} (41)

The results are reasonable in the sense that the production time are allotted to more profitable products (products 1 and 2) other than the less profitable product (product 3).

B. A Numerical Example of the Whole Problem P3

We considered an example of vehicle manufacturing system. The system is composed of 10 plants,and is built to produce 5 models of vehicles in a decision horizon of 520 periods (10 years). Of the five vehicle models,two are assumed to be popular through the decision horizon and the demands of them are relatively steady without much variance. The other three are assumed to be new models that are coming into the market at the beginning of the decision horizon,the beginning of the second year and the beginning of the third year,respectively. Their life time is assumed to be about 10 years. The demands of these three models are assumed to follow a Bass model[13],which sequentially increases,reaches its peak, and then decreases. The cumulative quantity of a Bass model quantity fits an S-shape curve.

We assumed $ 0 \le JPH_{ij0} \le 50$,for any $i$ and any $j$. Other given values are too many to be listed here and thus are omitted.

The problem was solved following the steps of the solution framework given in Section Ⅲ-C. One run of the solution process was as follows:

Step 1. One thousand samples of ${\pmb{JPH_0}}$ were uniformly and randomly generated.

Step 2. As a rough estimation of the samples$'$ performance, we respectively calculated the samples$'$ corresponding profits under one randomly generated demand instance. The normalized OPC was then obtained based on the sorted performances.

Step 3. It is calculated that the selected set should contain at least 30 designs to ensure with probability 0.95 that the selected set contains at least one actual top 5 % design. Thus the top 30 samples of the sorted are chosen as the selected set.

Step 4. To gain more accurate estimation of the selected samples$'$ performances so as to further distinguish them,we calculated their respective average profit under 10 randomly generated demand instances,and chose the design with the highest average profit as the final solution.

In Steps 2 and 4,the demand instances of the 5 vehicle models in the 10 years are generated as follows. For those two popular models, their demands are respectively generated randomly and uniformly within a given range. For those three that fit Bass model,the demands are generated based on the Bass model formula but with random noises injected into them. One example instance is given as Fig. 5.

Download:
Fig. 5. An example of generated demand instances.

The result of Step 2 shows that with the crude performance estimation the profit corresponding to the sorted best design is 17.3 % higher than that corresponding to the sorted worst one. This well indicates that a proper design of ${\pmb{JPH_0}}$ could make significant performance improvement and that one can actually achieve such improvement with optimization. The normalized OPC obtained in Step 2 is shown in Fig. 6,which fits a bell type OPC defined in OO theory,indicating that there are relatively few good designs,many intermediate and few bad designs (the rightmost and leftmost segments of the curve are steep). The final solution distinguished in Step 4 is shown in Table Ⅰ.

Download:
Fig. 6. The normalized OPC of the numerical example in Section Ⅳ-B (1 000 sampled designs, rough performance estimation model).

TABLE Ⅰ
FINAL SOLUTION OF THE NUMERICAL EXAMPLE

To evaluate the performance of the final solution,we compared its performance to all the other sampled designs and other 9,000 randomly and uniformly sampled designs with a more accurate performance estimation model,namely,to see how good the final solution$'$s performance is among a total number of 10 000 randomly and uniformly sampled designs. The result shows that the performance of the final solution ranks 242 in all the sampled designs,belonging to the top 5 % good enough solution set. This indicates that the OO algorithm indeed found a satisfactory solution. Furthermore,we obtained another OPC with the 10 000 designs$'$ sorted performances (as showed in Fig. 7). This OPC is believed to better approximate the true OPC compared to the one showed in Fig. 6 since a relatively large number of designs are investigated here with the more accurate performance estimation model. Because the true OPC of the problem cannot be obtained due to the problem complexity analyzed in Section Ⅲ-A,practically this OPC can be seen as a quasi-true OPC of the problem. From Fig. 6 and Fig. 7 we can see the estimated OPC obtained in Step 2 is of the same type as the quasi-true OPC. Thus we know the 1 000 designs sampled in Step 1 above can actually be a representation of the original search space and the OO method is rational to be applied to this problem.

Download:
Fig. 7. The quasi-true OPC of the numerical example in Section Ⅳ-B (10 000 sampled designs, more accurate performance estimation model)).

To gain a rough idea of the performance of the OO algorithm,we run the solution process for 10 replications as above and checked the performance of the final solution for each replication. The result shows that all of 10 runs find a final solution that is satisfactorily among the top 5 %. This demonstrates the OO algorithm$'$s feature of guaranteeing a high probability of finding satisfactory solutions. It should be noted that this validation step is not necessary in practical use.

Ⅴ. CONCLUSION

The planning model we proposed in this paper is important to help the decision making on the investment on the production lines to best balance between meeting the future demand and saving cost, and thus obtaining the maximum profit in the planning horizon. The challenge is the complex nature of the problem which makes the solution difficult to obtain For a given design,the uncertainty in demand makes the exact performance estimation impossible. If we require the estimation has a high confidence level,the computation burden would be significantly high. The OO method allows a rough model to estimate the performance of designs and only requires looking into a relatively small number of designs, and thus could be applied to our problem with notable reduction of the computation burden. This modeling framework and the optimization concept could provide helpful insights for similar scenario applications.

It should be pointed out that when determining which candidate solution can be selected as the final solution,more advanced methods,such as optimal computing budget allocation (OCBA)[14],could be applied to further enhance the efficiency of the solution framework. However,this is beyond the scope of this paper and is to be explored in our future work.

References
[1] Fleischmann B, Ferber S, Henrich P. Strategic planning of BMW's global production network. Interfaces, 2006, 36(3):194-208
[2] Kauder S, Meyr H. Strategic network planning for an international automotive manufacturer:balancing flexibility and economical efficiency. OR Spectrum, 2009, 31(3):507-532
[3] Bihlmaier R, Koberstein A, Obst R. Modeling and optimizing of strategic and tactical production planning in the automotive industry under uncertainty. OR Spectrum, 2009, 31(2):311-336
[4] Lin J T, Wu C H, Chen T L, Shih S H. A stochastic programming model for strategic capacity planning in thin film transistor-liquid crystal display (TFT-LCD) industry. Computers & Operations Research, 2011, 38(7):992-1007
[5] Zhang R Q, Zhang L K, Xiao Y Y, Kaku I. The activity-based aggregate production planning with capacity expansion in manufacturing systems. Computers & Industrial Engineering, 2012, 62(2):491-503
[6] Kulkarni A A, Shanbhag U V. Recourse-based stochastic nonlinear programming:properties and benders-SQP algorithms. Computational Optimization and Applications, 2012, 51(1):77-123
[7] Chien C F, Wu J Z, Wu C C. A two-stage stochastic programming approach for new tape-out allocation decisions for demand fulfillment planning in semiconductor manufacturing. Flexible Services and Manufacturing Journal, 2013, 25(3):286-309
[8] Ho Y C, Zhao Q C, Jia Q S. Ordinal Optimization:Soft Optimization for Hard Problems. New York:Springer, 2007.
[9] Birge J R, Louveaux F. Introduction to Stochastic Programming. New York:Springer, 1997.
[10] Sherali H D, Tuncbilek C H. A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. Journal of Global Optimization, 1992, 2(1):101-112
[11] Glover F, Woolsey E. Converting the 0-1 polynomial programming problem to a 0-1 linear program. Operations Research, 1974, 22(1):180-182
[12] IBM ILOG CPLEX. ILOG CPLEX 11. 0 User's Manual. France, 2007.
[13] Bass F M. A new product growth for model consumer durables. Management Science, 1969, 15(5):215-227
[14] Chen C H, Lin J W, Yücesan E, Chick S E. Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dynamic Systems, 2000, 10(3):251-270