Special Issue Paper

Journal of the Operational Research Society (2008) 59, 2–12. doi:10.1057/palgrave.jors.2602381 Published online 31 January 2007

Robust solutions and risk measures for a supply chain planning problem under uncertainty

C A Poojari1, C Lucas1 and G Mitra1

1Brunel University, Uxbridge, UK

Correspondence: CA Poojari, Centre for the analysis of Risk and optimization Modelling Applications (CARISMA), School of Information Systems, Computing and Mathematics, Brunel University, Uxbridge UB8 3PH, UK. E-mail: Chandra.Poojari@brunel.ac.uk

Received June 2006; Accepted November 2006; Published online 31 January 2007.

Top

Abstract

We consider a strategic supply chain planning problem formulated as a two-stage stochastic integer programming (SIP) model. The strategic decisions include site locations, choices of production, packing and distribution lines, and the capacity increment or decrement policies. The SIP model provides a practical representation of real-world discrete resource allocation problems in the presence of future uncertainties which arise due to changes in the business and economic environment. Such models that consider the future scenarios (along with their respective probabilities) not only identify optimal plans for each scenario, but also determine a hedged strategy for all the scenarios. We

  1. exploit the natural decomposable structure of the SIP problem through Benders' decomposition,
  2. approximate the probability distribution of the random variables using the generalized lambda distribution, and
  3. through simulations, calculate the performance statistics and the risk measures for the two models, namely the expected-value and the here-and-now.

Keywords:

supply chain planning, stochastic integer programming, Benders' decomposition, generalized lambda distribution, simulation, genetic algorithm

Top

1. An overview of supply chain decisions under uncertainty

Supply chain planning is a complex process whereby raw material procurement is followed by the manufacturing process and then finally the finished goods are distributed to the customers. The planning has to cope with short-term issues (operational planning such as the daily scheduling), medium-term (tactical planning such as the monthly scheduling) as well as long-term (strategic planning such as the capacity expansion or reduction). The area is a vibrant research field with a number of books devoted to this topic (Christopher, 1992; Shapiro, 2000). Much of the early research focused on solution algorithms such as the work of Geoffrion and Graves (1974) which used a Benders' decomposition approach to solve a single period multi-commodity production distribution problem. More recent work has focused both on more detailed model specifications and specialist algorithms to solve these more complex problems. Geoffrion and Powers (1995) describe how the industrial requirements for more detail in the model specification is still driving the research into developing algorithms to solve the resulting problems. Arntzen et al (1995) presented a global supply chain problem that minimizes cost and delivery time for Digital Equipment Corporation while meeting demand in a multi-period multi-commodity setting. Vidal and Goetschalckx (1997) review strategic models for planning global distribution and planning problems for supply chain planning and conclude that they are lacking in detail and more research is needed to fill this gap. Verter and Dasci (2002) developed a model for determining location of facilities and capacity configurations to be installed at each facility location. Conventionally, the managers in a manufacturing organization, ignore the interaction of the capacity and the inventory decisions by addressing them separately. In Bradley and Arntzen (1999), the authors develop a model that simultaneously plans capacity investment, inventory investment, and the production schedule while maximizing the return on assets. They model and analyse two cases, an office supplier and an electronic manufacturer, both involving strategic and tactical decisions.

While much of the earlier research work has looked at describing and solving a deterministic representation of the problem, more recently researchers have turned their attention to the modelling of uncertainty and the corresponding exposure of the risk thereby. Uncertainties can arise due to advances in technology, movements in foreign exchange rates, changes in international taxation schemes, and resource availability (in particular staff). The capturing of such risk further complicates the modelling of supply chain problems. Huchzermeier and Cohen (1996) develop a model that uses stochastic exchange rates and maximizes after tax profit while providing enough capacity to meet demand. In combining financing issues with decision making, supply chain planning now takes advantage of developments in mathematical finance. A number of strategic planning models use the techniques of option pricing and introduce a real options approach to capacity planning (Nembhard et al, 2000). Similarly, Haksoz and Seshadri (2007) consider incorporating of forward contracts for raw material deliveries to hedge against future raw material spot prices. They illustrate how the manufacturer's role can be changed to that of a speculator on movements in the future price of raw materials. From a management perspective, researchers have been investigating uncertainty and the modelling and control of risk. Christopher and Lee (2004) describe how the supply chain risk has increased driven by the changes in the business models used for modern supply chain planning. In adopting lean processes, these result in more outsourcing while relying on a much smaller supplier base. Their approach to improve this risk exposure is to encourage all the constituents in the supply chain process to provide more and better quality information. Brindley and Ritchie (2001) take this further and propose that relationship building and partnering is the most effective approach to risk management in the absence of a more quantitative approach. Their recent work (Ritchie and Brindley, 2007) proposes a framework for risk management. First risk drivers are determined, then by following a sequence of procedures the company can determine their actions in risk mitigation. Applying the process within a manufacturing company they found that it resulted in increased sharing of information, building of relationships, and the participation of all partners in the risk management process.

Quantitative models continue to play an important role. Scenario-based planning and analysis are particularly useful in times of a major structural change in capital intensive industries with long planning horizons, such as oil companies (Dempster et al, 2000), vehicle manufacturers (Eppen et al, 1989), and electricity suppliers (Robinson, 1988). They are built from a realistic combination of key driver values, such as interest-rates, inflation, demand for the products, fluctuation in prices, which are elaborated into fully fledged narratives by enriching them with information about dependent variables, certain events and the interactions between the many scenario elements. Several scenarios may need to be constructed to provide an insight into the risks, robustness and flexibility of various decisions and a defensible position from which to commit resources. Important issues in scenario generation are (i) comprehensibility, that is, it should capture all aspects, both extreme and normal instances, of the underlying distributions and (ii) consistency, that is, it must capture correlations among the stochastic data as well. Applications of scenario generation are found in the financial sector (see Carino et al, 1994; Mulvey, 1996; Dempster and Consigli, 1998). Hoyland and Wallace (1996) proposed an iterative algorithm that combines simulation, Cholesky decomposition and various transformations to generate scenarios for a Nordic asset management firm.

A mathematical programming problem in which some of the data are unknown, that is, they are subject to uncertainty, random influences, or statistical variations is called a stochastic programming (SP) problem. SP provides a general framework to model path dependence of the stochastic process within an optimization model. Furthermore, it permits uncountably many states and actions, together with constraints, time-lags etc. Unlike dynamic programming, SP separates the model formulation activity from the solution algorithm. One advantage of this separation is that it is not necessary for SP models to obey the same mathematical assumptions. This leads to a rich class of models for which a variety of algorithms can be developed. SP formulations, however, can lead to very large-scale problems. This requires the development of efficient solution methods in order to process progressively larger models.

Top

2. Outline of the paper

Our approach in this paper is a contribution towards business analytics in supply chain. We formulate a practical strategic supply chain model as a two-stage SP problem. We process the ex-ante here-and-now decision problem using Benders' decomposition. Ex-post analysis is carried out in order to evaluate the performances of the here-and-now and the expected-value decisions. In the absence of knowledge of the probability distribution of the demand, we construct an approximate probability distribution using the generalized lambda distribution (GLD). The parameters of the GLD are estimated by processing a non-linear optimization problem using a Genetic Algorithm. The performance of the decisions are evaluated on the scenarios generated using the GLD. Currently, researchers either use SP or simulation in order to model supply chain problems having uncertain parameter values. Our two-faceted approach that combines the SP modelling and simulation is the main contribution in this paper.

In Section 3, we discuss the use of SP for modelling risk-based decision making in Supply chain. In Section 4, we formulate a strategic supply chain planning problem having uncertain demand as a stochastic integer programming (SIP) problem. The resulting large-scale optimization problem is processed using Benders' decomposition which is detailed in Section 5. In Section 6, we show how the GLD is used in order to construct an approximate probability distribution of the uncertain demand. The parameters in the generalized lambda are estimated by processing a non-linear optimization problem using a Genetic Algorithm, and the correlation among the demand for different time period, products and customer zones is captured using Kendall's Tau measure. We then construct a simulation model and for the alternative decisions compute the Value-at-Risk (VAR) and the Conditional-Value-at-Risk (CVAR). Finally in Section 7, we summarize the results of our investigations.

Top

3. SP for modelling of risk in supply chain

Location of production assets and the expansion or reduction of their capacities form a crucial aspect of many strategic planning applications. Examples of such applications can be found in heavy process industries (Manne, 1967), communication networks (Chang and Gavish, 1993; Laguna, 1998), electric utilities (Murphy et al, 1987; Murphy and Weiss, 1990), automobile industries (Eppen et al, 1989), service industries (Berman and Ganz, 1994; Berman et al, 1994) and in electronic goods and semiconductor industries (Rajagopalan et al, 1998; Berman and Hood, 1999; Swaminathan, 2000). In all these applications, the expansion of production capacity requires the commitment of substantial capital resources over long periods of time. Furthermore, the economies of scale in the expansion costs, as well as the uncertainties in the long range forecasts of costs and demands, make these decision problems very complex. Consequently, quantitative models for economic capacity expansion planning has been the subject of intense research since the early 1960s. Conventionally, in the context of Operations Research, mixed integer programming (MIP) models have been formulated for determining strategic decisions. Such models are often inadequate because they completely ignore future uncertainties. A simplified yet pragmatic approach to capture some aspects of these uncertainties is to introduce a set of 'scenarios' representing possible future states of the world. Each scenario is associated with a probability level representing the decision maker's expectation of the occurrence of a particular scenario. This class of models which capture both the optimum resource allocation paradigm and the randomness of the model parameters, are known as SP problems. SP models with integer variables are known as SIP.

SP models are ideally suited for analysing resource acquisition plans since they explicitly consider randomness and quantify uncertainty governing the key parameters of the model. As a consequence the optimum decisions for strategic plans and tactical operations are more flexible or robust in comparison with decisions obtained by applying deterministic models. SP models have been successfully applied to strategic planning problems for example: electric utility planning (Bienstock and Shapiro, 1988), goods distribution (Cheung and Powell, 1996), capacity planning (Modiano, 1987; Escudero et al, 1993; Wagner and Berman, 1995), communication network planning (Fantauzzi et al, 1996), transportation planning and vehicle routing (Federgruen and Zipkin, 1984; Laporte et al, 1994).

An important class of stochastic models is the two-stage stochastic linear program with recourse stated as:

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

where Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author, xi is the vector formed by the components of qT, h, B and D, and Exi denotes mathematical expectation with respect to xi. The vector x represents the first-stage (strategic) decisions to be taken without full information on the random variable xi. Later, complete information is received on the realization of the random vector xi, then, second-stage (operational) or corrective actions y are taken. The expected value of the second-stage cost function ExiQ(x,xi) is referred to as the recourse function (Birge and Louveaux, 1997).

Since the SP model involves submodels describing a set of scenarios of the company's future (uncertain) operations, they usually lead to problems of substantial dimensions. A detailed description of how the hierarchical structure of planning systems can be exploited for building and solving two-stage and multistage stochastic decision models can be found in Birge and Louveaux (1997), Dempster et al (1983), Stougie (1987), Bitran and Tirupati (1993).

While a decision analysis (Keeney and Raiffa, 1976) approach is well suited to achieving coherence and explicit communication, the skill in this area is to get an acceptable amount of detail into the model for credibility, without it becoming too complicated and confusing. SP being an extension of Linear/MIP allows processing of resource allocation models having a number of variables and constraints. As in Linear/MIP there is no coupling between the SP modelling and the SP solution algorithms hence sophisticated algorithms can be tuned to exploit the model structure. With the availability of parallel communication protocol, real-life models having over a million scenarios have been processed (Fragniere et al, 2000) on desktop PCs.

SP provides three ways of analysing such large-scale models

  • construct a separate strategy for each scenario and test whether or not such strategies are acceptable for the other scenarios;
  • construct a solution that hedges against all the scenarios with respect to some metric such as the expected cost;
  • construct a solution that satisfies a set of conditions with a given level of reliability.

Top

4. A supply chain capacity planning model under uncertain demand

Our model represents the entire manufacturing supply chain, from the acquisition of raw material to the delivery of the final products. In order to capture the interactions among different echelons of the manufacturing process at each time period tset symbolT, the network is simplified to four echelons related to production, packing, distribution and customer zones. In Figure 1, PR, PC, DC, and CZ denote the sets of production plants, packing plants, distribution centres and customer zones, respectively. The problem is a multi-period multiechelon model representing strategic decisions, such as site locations, choices of production, packing and distribution lines and their capacity increment or decrement policies.

Figure 1.
Figure 1 - Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

The supply chain planning network.

Full figure and legend (80K)

The complete formulation of the model (Baricelli, 1996) can be divided into three main components.

4.1. Logical constraints

These are purely strategic constraints and ensure logical consistencies; a typical constraint group is shown below,

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

where rtil is a binary variable determining if line l is operational at site i time t or not, Mi is the maximum number of lines allowed at site i, and zti is a binary variable indicating if site i is open time t (zti=1) or not (zti=0).

Other logical constraints are modelled to determine when sites or lines are closed down or newly opened. These are necessary since costs and penalties are incurred whenever these events occur.

4.2. Capacity constraints

The second major component of the model comprises constraints linking strategic and operational variables. Most of these restrictions concern site capacities. A typical group of production capacity constraints are illustrated below,

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

where ftilp is the fraction of line capacity l required to produce one unit of product p time t at site i, qtilp is the amount of product p produced on line technology type l at site i time t, etil is the efficiency of line type l at site i time t, and Ctil is a reporting variable representing the number of lines of technology l at site i time t.

4.3. Demand constraints

The last major component of the model concerns operational constraints. The bulk of these represent material balances. The demand constraints are illustrated below

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

where muthp is the shortage quantity of product p at customer zone h time t, Dthp is the demand of product p from customer h time t, Ftkhp is the amount of product p sent to customer h from distribution centre k, time t.

The uncertainty in the demand for the end-products is captured through a set of scenarios. The first stage decisions are strategic (binary and integer) and consequently are not indexed by this new set. Whereas all the operational decisions are now second stage decisions and incorporate the scenario index, s. Thus the number of constraints in the second and third components of the model grow in dimension by this new index set. Taking this into account and for convenience, we set out the most general formulation of the problem as a two-stage SIP model, P2SIP.

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

where x=(xI,xB), xIset symbolZn1', xBset symbol{0,1}n1", Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author, ysgreater than or equal to0 S denotes the set of scenarios, whereby s=1,...|S|; ps denotes probability of occurrence of scenario s; x denotes the first-stage variables; ys denotes the second-stage recourse variables; bset symbolRm1, hset symbolRm2, dsset symbolRm3, cset symbolRn1, fset symbolRn2, Aset symbolRm1timesn1, Bset symbolRm2timesn1, Dset symbolRm2timesn2, Eset symbolRn2timesn2.

Table 1 summarizes a single scenario deterministic MIP model presented as a detailed planning model (in our case there are 100 scenarios).


Top

5. Computational investigation: processing the SIP decision problem

A distinguishing feature of two- and multi-stage SP model is that the dynamics of uncertainty is discretized as a scenario tree in which nodes represent probabilistic states of information, which is supplemented by a linear dynamical system of vectors representing auxillary aspects of state. The structure of the resulting dual-block angular system can be decomposed effectively to compute solutions for progressively larger models in reasonable time. There are two types of decomposition-based approaches depending on whether the scenario tree is split according to time stages—primal decomposition or scenarios-dual decomposition. These decomposition-based algorithms are iterative procedures generating progressively better solutions. Each iteration consists of solving a master problem and several independent subproblems—a reason why these methods are specially suited for parallelization. The appeal of such techniques lies in the fact that they solve the original problem by iteratively solving a sequence of manageable subproblems.

5.1. Benders' decomposition

The L-shaped decomposition (Van Slyke and Wets, 1969) is derived from the observation that the recourse cost function Q(x, xi(omega)) are convex and polyhedral (piece-wise) linear. The expected recourse cost Q(x)(=ExiQ(x, xi(omega))) is also convex and polyhedral when the uncertain parameters follow a finite, discrete distribution (Wets, 1974). Based on these observations, the implicit form of Q(x) can be restated in terms of outer linearization of the nonlinear recourse function. From convexity of Q(x,xi(omega)), it follows that a linear approximation is a lower support. The method solves an approximation of the two-stage linear program using an outer linearization of Q(x). Two types of constraints are sequentially added: (i) feasibility cuts determining {x|Q(x)<+infinity} and (ii) optimality cuts which are linear supports of Q(x) on its domain of finiteness. The basic idea of the L-shaped method is to approximate the nonlinear recourse function in the objective of these problems. A general principle behind this approach is that, since the recourse function involves a solution of all second-stage recourse linear programs, we would like to avoid numerous function evaluations for it. We therefore use that term to build a master problem in x but we evaluate the recourse function exactly as a sub-problem.

The method can be visualized as solving a problem associated with each node of the scenario tree. These problems are formed by the realization of the associated random parameters. The tree is traversed forwards and backwards, with information from the solution to each nodal LP problem being passed to its immediate descendants by the formation of their right-hand side and to its immediate ancestors in the form of cuts. This method has also been generalized to multiple stages (Birge, 1985).

Our computations were performed on Windows 2000 having 2.4 GHz and 2 MB RAM. We used CPLEX (ILOG, www.ilog.com) version 9 as the solver subroutine. We investigate the solutions to three formulations of the supply chain problem. First, we consider the expected value model in which the stochastic demands are replaced by the expected value. Second, we consider the wait-and-see problems for each scenario, this corresponds to analysing each scenario separately. Finally, we compute the hedged solution by solving the here-and-now problem. Table 2 shows the objective values and the time taken in order to process the expected value, here-and-now, and the wait-and-see problems.


Top

6. Simulation and back testing

6.1. Experimental framework

SP provides a framework for a hedged strategy (decisions), whereas simulation provides a framework for evaluating such a strategy. By combining SP and simulation we bring together the two frameworks which contribute towards the problem owner's insight into the model. Quantitative researchers and theoreticians have been pushing to integrate stress tests within the general risk management framework. In part this has taken the form of exploring mathematical techniques such as extreme value theory—a statistical approach to improve estimates of the tails or extremes of distributions—to see whether rare events can be treated in a way that is more rigorous, and more tractable.

Stress tests is a mix of quantitative technique, expert judgement, a behavioural approach and market intuition. This is particularly true in terms of specifying how fundamental risk factors interact with one another in a stressed market: known sensitivities and scenarios have to be layered into one another and made to behave in an economically plausible way, using expert judgement.

In order to test the robustness and the risk measure of the expected-value and the here-and-now decisions, we evaluate them using out-of-sample scenarios. Such out-of-samples could have been generated easily had we known the underlying probability distribution of the demand. In our case, however, the initial (100) demand scenarios were generated by the domain expert through a combination of subjective and objective techniques.

The demand vectors are indexed over the different products, customers, and time-periods. Therefore, the assumption of independence among the different components of the demand is not appropriate. In case the marginal probability distribution of the components are known, then multi-variate copulas could be constructed. In the absence of closed form representation for the marginal distribution of the demand and the lack of knowledge about the dependence between the components, it is not possible to use many of the established statistical techniques in order to construct the multivariate joint distribution of the demand vector. Therefore our approach is to first approximate the marginal distributions using the GLD and then to combine the marginal distribution using the correlation structure among the components. In Algorithm 6.1 we describe our pseudocode for simulation. In this pseudocode, we compute the Value-at-Risk (VAR) and the Conditional-Value-at-Risk (CVAR) for the expected-value and the here-and-now decisions.

Algorithm 6.1
 

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

6.2. Generalized lambda distribution

The inverse problem of finding the probability distribution from a given moment sequence is a hard problem as shown first by Stieltjes. The GLD (Ramberg and Schmeiser, 1974) is a four parameter generalization of Tukey's Lambda family (Hastings et al, 1947), that has proved useful in a number of different applications. GLD can assume a wide variety of shape, and offers risk mangers flexibility in modelling a broad range of probability distributions. Due to its versatility, however, obtaining approximate parameters for the GLD is very challenging (Karian and Dudewicz, 2000). One of the methods for estimating the parameters of GLD is based on matching the first four moments of the empirical data. Tukey's lambda family of distribution is defined by the quantile function Q(u).

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

A four parameter generalization of Equation 5 was proposed by Ramberg and Schmeiser. For this generalization, the quantile function is given by

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

(Ramberg et al, 1979) note that the proposed distribution in Equation (6) is not defined for certain combinations of the parameters. Freimer et al (1988) devise a different parametrization for the GLD, denoted as FMKL

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

This parametrization is well defined over the entire two-dimensional plane for the parameter lambda3 and lambda4. However, in order to have a finite kth order moment it is necessary that min(lambda3,lambda4)>=-1/k. Using the relationship Q(u)=x and F(x)=u, we get f(x)=f(Q(u)). Since f(x)=dF/dx, therefore f(x)=du/dx=du/dQ(u)=1/(dQ(u)/du)=lambda2/(ulambda3-1+(1-u)lambda4-1).

6.3. An optimization problem for matching moments

Given a GLD with quantile function Q(u), we need to find the parameters lambda1,lambda2,lambda3 and lambda4 such that the mean (mu), variance (sigma2), skewness (alpha3) and kurtosis (alpha4) of the GLD match the corresponding mean Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author, variance Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author, skewness Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author, and kurtosis Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author of the sample. The FMKL parameter for the quantile function can be rewritten as

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

P(u)=u3lambda/lambda3-(1-u)lambda4/lambda4, qk= the kth central moment of F-1(u), and pk= the kth raw moment of P(u).

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

where pk=integral01(ulambda3/lambda3-(1-u)lambda4/lambda4)kdu. Using Binomial expansion on pk, we obtain

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

where beta(a, b)=integral01ua-1(1-u)b-1du. Since the beta function is defined only for the positive values of a and b, we have

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

The first four raw moments of the distribution are given as follows:

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Substituting the Equations 14, 15 16, 17 in 9, 10, 11 and 12 we get,

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

The values of the parameters lambda3 and lambda4 of the GLD can be obtained by solving the optimization problem

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

where

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Once the values for lambda3 and lambda4 are obtained, then lambda1 and lambda2 can be computed using Equations 22 and 23.

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

The optimization problem 20 is non-linear and non-convex. Some of the existing techniques to solve it include least square (Ozturk and Dale, 1985), Starship method (King and MacGillivray, 1999), Downhill simplex (Nelder and Mead, 1965), Powell's method (Powell, 1962). We develop a steady-state GA that uses 'overlapping' populations and a parameter-less penalty function in order to process constrained optimization problems (see Poojari and Varghese (2007) for details). Our GA start out with an initial population of possible solutions to a given problem where each individual is represented using some form of encoding as a chromosome. Newly generated offspring are added to the population, then the worst individuals are destroyed. The new offspring may or may not make it into the population, depending on whether they are better than the worst in the population. The individuals in the population are represented as real arrays where the arrays represent the solution vector to the optimization problem. These chromosomes are evaluated for their fitness. The fitness function is designed to provide greater emphasis on optimality during the initial generations of the GA, so as to avoid the algorithm converging to a local optima. Based on their fitness as a criterion, certain chromosomes in the population are selected for reproduction. These selected individuals are manipulated by crossover and mutation operators. The crossover operator is applied to a pair of selected parents to create offspring, and the mutation operator is used as a slight modification to this offspring, or to the remaining members of the population (Table 3).


6.4. The mixing model

The demand vectors are indexed over multiple time-periods, products, and customer zones. Through the GLD we approximate the marginal probability distribution of each component of the demand vector. However, these components may be correlated. For instance, the demand for a given product in one time-period may influence the demand for the same/different product in another time-period. We use demand scenarios in order to approximate the correlation among the components.

It is well known that the Pearson correlation matrix measures the linear correlation, and the rank-based correlation coefficients such as the Kendall's tau or the Spearman's rho measure the monotonic association. The rank coefficients are able to detect the correlation when the correlation is nonlinear but monotonic and is also known to be robust is the presence of outliers.

We generate the random vectors (eta) using the model

Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

where Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author is the ith marginal distribution denoted by the GLD G(lambda1i,lambda2i,lambda3i,lambda4i), and Xirho is the mtimesm Kendall's tau correlation matrix of the original scenarios. The details of the simulation are shown in Table 4.


We simulate the performance of the here-and-now and the expected value solutions. Theoretically it is known that the here-and-now solution provides a hedged solution and is more robust, therefore it should have lower VAR and CVAR values. Table 5 shows the 95% VAR and the CVAR values for the expected value and the here-and-now solutions. Figure 2 shows the distribution of the cost for the expected value and the here-and-now solution, respectively.

Figure 2.
Figure 2 - Unfortunately we are unable to provide accessible alternative text for this. If you require assistance to access this image, please contact help@nature.com or the author

The distribution of the cost for the expected value and the here-and-now solution.

Full figure and legend (129K)


Top

7. Discussion and conclusion

We have investigated a strategic capacity planning problem having uncertain demand formulated as a two-stage SIP problem.

The underlying optimization is NP-hard due to the presence of integer and binary variables. These discrete variables correspond to the strategic decisions such as site locations, choices of production, packing and distribution lines, and the capacity increment or decrement policies. We have implemented Benders' decomposition to process the problem. Further, we verify the robustness of the solution obtained for the stochastic problem through simulation. In order to do this, we have developed a GLD for the demand. The parameters for the GLD are estimated by processing a non-linear and non-convex optimization problem using a steady-state Genetic algorithm. We evaluate the ex ante decisions of the expected-value and the here-and-now optimization problems through simulation of the random demand. Also, by fixing the first-stage decisions in the underlying optimization problem, we compute well-known measures of risk such as the VAR and the CVAR. We, thus, provide a framework for obtaining robust solutions and computing the risk measures for a practical supply chain planning problem.

Top

References

  1. Arntzen B, Brown G, Harrison TP and Trafton L (1995). Global supply chain management at digital equipment corporation. Interfaces 1(25): 69–93.
  2. Baricelli P (1996). An investigation into a manufacturing and supply chain planning problem under uncertainty. Master's thesis, Department of Mathematics and Statistics, Brunel University, West London.
  3. Berman O and Ganz Z (1994). The capacity expansion problem in the service industry. Comput Opns Res 21: 557–572. | Article |
  4. Berman O, Ganz Z and Wagner J (1994). A stochastic optimization model for planning capacity expansion in a service industry under uncertain demand. Naval Res Logist 41: 545–564. | Article | ISI |
  5. Berman O and Hood S (1999). Capacity optimization planning system (caps). Interfaces 29: 31–50. | ISI |
  6. Bienstock D and Shapiro J (1988). Optimizing resource acquisition decisions by stochastic programming. Mngt Sci 34: 215–229.
  7. Birge J (1985). Decomposition and partitioning methods for multi-stage stochastic linear programs. Opns Res 33: 989–1007.
  8. Birge J and Louveaux F (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. Springer-Verlag: New York.
  9. Bitran G and Tirupati D (1993). Hierarchial production planning. Handbooks in Operations Research and Management Science: Logistics of Production and Inventory. North-Holland: Amsterdam.
  10. Bradley J and Arntzen B (1999). The simultaneous planning of production, capacity, and inventory in seasonal demand environments. Opns Res 47: 795–806.
  11. Brindley C and Ritchie R (2001). The information-risk conundrum. Market Intell Plann 1(19): 29–37.
  12. Carino D, Kent R, Myers D, Stacy C, Sylvanus M, Turner A, Watababe K and Ziemba W (1994) . Russell–Vasuda kasai model: an asset liability model for Japanese insurance company using multi-stage stochastic programming. Interfaces, 24(1): 29–49. | ISI |
  13. Chang S-G and Gavish B (1993). Telecommunications network topological design and capacity expansion. Telecommun Syst 1: 99–131. | Article |
  14. Cheung R and Powell W (1996). Models and algorithms for distribution problems with uncertain demands. Transport Sci 30: 43–59. | ISI |
  15. Christopher M (1992). Logistics and Supply Chain Management. Pitman Publishing: London.
  16. Christopher M and Lee H (2004). Mitigating supply chain risk through improved confidence. Int J Phys Distrib Logist Mngt 4: 388–396. | Article |
  17. Dempster M and Consigli G (1998). The calm stochastic programming model for dynamic asset-liability management. In: Mulvey JM and Ziemba WT (eds). World Wide Asset and Liability Modelling. Cambridge University Press: Cambridge, pp 464–500.
  18. Dempster M, Fisher M, Jansen L, Lageweg B, Lenstra J and Kan A (1983). Analysis of heuristics for stochastic programming—results for heirarchical scheduling problems. Math Opns Res 8: 525–537.
  19. Dempster M, Pedrón NH, Medova E, Scott J and Sembos A (2000). Planning logistic operations in the oil industry. J Opl Res Soc 51: 1271–1288. | Article |
  20. Eppen G, Martin R and Schrage L (1989). A scenario approach to capacity planning. Opl Res 37: 517–525.
  21. Escudero L, Kamesam P, King A and Wets R-J (1993). Production planning via scenario modelling. Ann Opns Res 43: 311–335.
  22. Fantauzzi F, Gaivornski A and Messina E (1996). Lecture notes on economics and mathematical systems: Network optimization. In: Pardalos M., Hearn D and Hager WW, editors. Decomposition Methods for Network Optimization Problems in the Presence of Uncertainty, Vol. 450. Springer: Berlin, pp 234–248.
  23. Federgruen A and Zipkin P (1984). A combined vehicle routing and inventory allocation problem. Opns Res 32: 1019–1037.
  24. Fragniere E, Gondzio J and Vial J-P (2000). Building and solving large-scale stochastic programs on an affordable distributed computing system. Ann Opns Res 99: 167–187. | Article |
  25. Freimer M, Mudholkar G, Kollia G and Lin C (1988). A study of the generalized Tukey lambda family. Commun Statist—Theory Methods 17: 3547–3567.
  26. Geoffrion A and Graves G (1974). Multicommodity distribution system design by bender's decomposition. Mngt Sci 20: 822–844.
  27. Geoffrion A and Powers R (1995). Twenty years of strategic distribution systems design: An evolutionary perspective. Interfaces 25(5): 105–128.
  28. Haksoz C and Seshadri S (2007). Supply Chain operations in the presence of a spot market: a review with discussion. J Opl Res Soc 58: 1412–1429.
  29. Hastings C, Mosteller F, Tukey JW and Winsor CP (1947). Low moments for small samples: A comparative study of order statistics. Ann Math Statist 18: 413–426. | ISI |
  30. Hoyland K and Wallace S (1996). Generating scenario trees for multi-stage decision problems. Mngt Sci 26: 1–13.
  31. Huchzermeier A and Cohen M (1996). Valuing operational flexibility under exchange rate risk. Opns Res 44: 100–113.
  32. Karian Z and Dudewicz E (2000). Fitting Statistical Distributions: The Generalized Lambda Distribution and Generalized Bootstrap Methods. CRC Press: Boca Raton, FL.
  33. Keeney R and Raiffa H (1976). Decisions with Multiple Objectives: Preferences and Value Trade-offs. Wiley: New York.
  34. King RAR and MacGillivray HL (1999). A starship estimation method for the generalized lambda distributions. Austral New Zealand J Statist 41: 353–374. | Article | ISI |
  35. Laguna M (1998). Applying robust optimization to capacity expansion of one location in telecommunications with demand uncertainty. Mngt Sci 44: 101–110.
  36. Laporte G, Louveaux F and Hamme LV (1994). Exact solution to a location problem with stochastic demands. Transport Sci 28: 95–103. | ISI |
  37. Manne A (ed). Investments for Capacity Expansion. The MIT Press: Cambridge.
  38. Modiano E (1987). Derived demand and capacity planning under uncertainty. Opns Res 35: 185–197.
  39. Mulvey J (1996). Generating scenario for the towers perrin investment system. Interfaces 26: 1–13. | ISI |
  40. Murphy F and Weiss HJ (1990). An approach to modeling electric utility capacity expansion planning. Naval Res Logist 37: 827–845. | Article | ISI |
  41. Murphy F, Sen S and Soyster A (1987). Electric utility expansion planning in the presence of existing capacity: A nondifferentiable, convex programming approach. Comput Opns Res 14: 19–31. | Article |
  42. Nelder JA and Mead R (1965). A simplex method for function minimization. Comput J 7: 308–313. | ISI |
  43. Nembhard H, Shi L and Park C (2000). Real option models for managing manufacturing system changes in the new economy. Eng Econom 45: 232–258. | Article |
  44. Ozturk A and Dale R (1985). Least squares estimation of the parameters of the generalized lambda distribution. Technometrics 27: 81–85. | Article | ISI |
  45. Poojari CA and Varghese B (2007). Genetic algorithm based technique for solving chance constrained problems. Eur J Opl Res, doi:10.1016/j.ejor.2006.06.045. | Article |
  46. Powell M (1962). An iterative method for finding stationary values of a function of several variables. Comput J 5: 147–151.
  47. Rajagopalan S, Singh M and Morton T (1998). Capacity expansion and replacement in growing markets with uncertain technological breakthroughs. Mngt Sci 44: 12–30.
  48. Ramberg J and Schmeiser B (1974). An approximate method for generating asymmetric random variables. Commun ACM 17: 78–82. | Article | ISI |
  49. Ramberg J, Dudewicz E, Tadikamalla P and Mykytka E (1979). A probability distribution and its uses in fitting data. Technometrics 21: 201–214.
  50. Ritchie B and Brindley C (2007). An emergent framework for supply chain UK management and performance measurment. J Opl Res Soc 58: 1398–1411.
  51. Robinson JB (1988). Loaded questions: New approaches to utility forecasting. Energy Pol 16: 58–68. | Article | ISI |
  52. Shapiro J (2000). Modeling the Supply Chain. Brooks/Cole-Thomson Learning: Pacific Grove, CA.
  53. Stougie R (1987). Design and analysis of algorithms for stochastic integer programming. CWI Tract 37: 48–62.
  54. Swaminathan J (2000). Tool capacity planning for semiconductor fabrication facilities under demand uncertainty. Eur J Opl Res 120: 545–558. | Article |
  55. Van Slyke RM and Wets RJ-B (1969). L-shaped linear programs with application to optimal control and stochastic programming. SIAM J Appl Math 17: 638–663. | Article |
  56. Verter V and Dasci A (2002). The plant location and flexible technology acquisition problem. Eur J Opl Res 136: 366–382. | Article |
  57. Vidal C and Goetschalckx M (1997). Strategic production—distribution models: A critical review with emphasis on global supply chain models. Eur J Opl Res (98), 1–18.
  58. Wagner J and Berman O (1995). Models for planning capacity expansion of convenience stores under uncertain demand and the value of information. Ann Opns Res 59: 19–44. | Article |
  59. Wets RJ-B (1974). Stochastic programs with fixed recourse: The equivalent deterministic program. SIAM Rev 16: 309–339. | Article | ISI |