On modelling planning under uncertainty in manufacturing
Abstract
We present a modelling framework for two-stage and multi-stage mixed 0-1 problems under uncertainty for strategic Supply Chain Management, tactical production planning and operations assignment and scheduling. A scenario tree based scheme is used to represent the uncertainty. We present the Deterministic Equivalent Model of the stochastic mixed 0-1 programs with complete recourse that we study. The constraints are modelled by compact and splitting variable representations via scenarios.
Full text
Statistics & Operations Research Transactions SORT 31 (2) July-December 2007, 109-150 Statistics & Operations Research Transactions On modelling planning under uncertainty in manufacturing∗ c Institut d’Estad´ ıstica de Catalunya [email protected] ISSN: 1696-2281 www.idescat.net/sort A. Alonso-Ayuso1,L.F.Escudero 2and M.T. Ortu˜ no3 1,2Dpto. de Estad´ıstica e Investigaci´on Operativa, Universidad Rey Juan Carlos (Madrid) 3Dpto. de Estad´ıstica e Investigaci´on Operativa, Universidad Complutense de Madrid (Madrid) Abstract We present a modelling framework for two-stage and multi-stage mixed 0−1 problems under uncertainty for strategic Supply Chain Management, tactical production planning and operations assignment and scheduling. A scenario tree based scheme is used to represent the uncertainty. We present the Deterministic Equivalent Model of the stochastic mixed 0−1 programs with complete recourse that we study. The constraints are modelled by compact and splitting variable representations via scenarios. MSC: 90C06, 90C10, 90C11, 90C15, 90C17, 90C90 Keywords: Supply chain; BoM; strategic planning; scheduling; uncertainty; stochastic programming; Branch-and-Fix Coordination 1 Introduction 1.1 Motivation and organization of the work Very frequently, mainly in problems with a given time horizon to exploit, some coefficients in the objective function and the right-hand-side (rhs) vector and, to a lesser *This research has been partially supported by grant MTM2006-14961-C05-05 from MCYT, grant TIN200606190 from DGI, and GRUPOS79/04 from the Generalitat Valenciana, Spain. The paper is an extension and updating of the work (A. Alonso-Ayuso, L.F. Escudero and M.T. Ortu˜ no, 2005). 1Dpto. de Estad´ ıstica e I.O. Universidad Rey Juan Carlos. M´ ostoles (Madrid). Spain, e-mail: [email protected] 2Dpto. de Estad´ ıstica e I.O. Universidad Rey Juan Carlos. M´ ostoles (Madrid). Spain. Corresponding author: [email protected] 3Dpto. de Estad´ ıstica e I.O. Universidad Complutense de Madrid (Madrid). Spain, e-mail: [email protected] Received: May 2007
110 On modelling planning under uncertainty in manufacturing extent, the constraint matrix are not known with certainty when decisions are to be made, but certain information is available. The paper deals with important manufacturing problems. With this objective we follow the classic taxonomy of planning/scheduling problems in strategic, tactical and operational problems proposed by [11]. The models of most of the problems require 0−1 variables and, so, we will use a modelling methodology based on Stochastic Integer Programming (SIP). It has a broad field of application, mainly, in production planning and logistics of transportation and distribution, see [2–4, 6, 7, 38, 41, 52, 56, 57, 61, 73, 82], among others. See in [54] a good survey of coordination mechanisms of supply chain systems. Many of the SIP approaches represent the uncertainty by a set of scenarios. The problem is formulated by the so-called Deterministic Equivalent Model (DEM), and use Benders decomposition [10, 17, 20, 23, 36, 53, 73], Lagrangian decomposition [22, 42, 45, 51, 72, 75–77, 84], disjunctive decomposition [63, 79], stochastic branchand-cut [78], Benders decomposition based branch-and-bound [80], branch-and-fix coordination [3, 5, 7, 37] and stochastic dynamic programming [26], among others. See also [74]. Most of the approaches deal with the optimization of the objective function expected value alone. However, there are some approaches that additionally deal with meanrisk measures, by considering semi-deviations [66], excess probabilities [76] and conditional value-at-risk [70, 77] as risk measure-based functions to optimize. See also [1,7,57,74, 86,89], among others. The remainder of the paper is organized as follows. Sections 1.2 and 1.3 present the objective functions min expected value and min mean-risk to optimize. Subsections 1.4 and 1.5 introduce the stochastic modelling paradigm to use in the rest of the work. Section 2 presents the problem and modelling approach for strategic Supply Chain Management determining the production topology and product selection via a twostage complete recourse mixed 0−1DEM. Section 3 presents the strategic Multiperiod Single Sourcing Problem (MPSSP) and its modelling as a two stage complete recourse mixed 0−1 problem. Section 4 presents the tactical single level Production Planning and Raw Material Supplying problem as a multi-stage mixed 0−1 problem. Section 5 deals with the difficult tactical multilevel Supply Chain Management problem as a multistage complete recourse continuous problem. Section 6 presents the difficult operational Stochastic Sequencing and Scheduling (S3) problem for assigning the operations to a time schedule with limited resources as a multi-stage complete recourse pure 0−1 problem. Finally, Section 7 concludes.
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 111 1.2 Objective function expected value Consider the following deterministic model min cx +ay subject to (s.t.) Ax +By =b x∈{0,1}n,y≥0, (1) where cand aare the n-andnc-row vectors of the objective function coefficients, respectively, bis the column right-and-side rhs m-vector, Aand Bare the m×nand m×ncconstraint matrices, respectively, xand yare the n–andnc–vectors of the 0−1and continuous variables to optimize over a set of stages T, respectively, and m,nand nc are the number of constraints, and the 0−1 variables and continuous variables, respectively. The model must be extended in order to deal properly with the uncertainty in the values of some parameters. Thus, an approach to model the uncertainty in the problem data is needed. Definition 1 Astage of a given time horizon is a set of time periods where the realization of the uncertain parameters takes place. Definition 2 Ascenario is one realization of the uncertain parameters along the stages of the given time horizon. Definition 3 Ascenario group for a given stage is the set of scenarios with the same realization of the uncertain parameters up to the stage. t=1t=2t=3t=4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Ω=Ω 1={10,11,...,17};Ω2={10,11,12} G={1,...,17};G2={2,3,4} N9={1,4,9};γ(9) =4 Figure 1: Scenario tree
112 On modelling planning under uncertainty in manufacturing Many approaches at present for stochastic programming and, certainly, SIP are scenario-based approaches to deal with the uncertainty. To illustrate this concept, see [4], consider Figure 1: each node in the figure represents a point in time where a decision can be made. Once a decision has been made, some contingencies can occur (e.g., in this example the number of contingencies is three for time period t=2), and information related to these contingencies is available at the beginning of the stage (here, time period). This information structure is visualized as a tree, where each root-to-leaf path represents one specific scenario and corresponds to one realization of the whole set of the uncertain parameters. Each node in the tree can be associated with a scenario group, such that two scenarios belong to the same group in a given stage, provided that they have the same realizations of the uncertain parameters up to the stage. Accordingly with the non-anticipativity principle, see [20,71], both scenarios should have the same value for the related variables with the time index up to the given stage. Let the following notation related to the scenario tree: T,set of stages along the time horizon. T−≡ T − {|T |}. Ω,set of scenarios. G,set of scenario groups, so that we have a directed graph where Gis the set of nodes. Gt,set of scenario groups in stage t, for t∈T(Gt⊆G). Ωg,set of scenarios in group g, for g∈G(Ωg⊆Ω). γ(g),immediate ancestor node of node g, for g∈G. Ng,set of scenario groups {k}such that Ωg⊆Ωk, for g∈G(Ng⊂G). That is, set of ancestor scenario groups to scenario group g, including itself. Ng,set of successor nodes to node g. That is, set of successor scenario groups to scenario group g, including itself. wg,weight factor representing the likelihood that is associated with scenario group g, for g∈G.Note:wg=ω∈Ωgwω, where wωgives the likelihood that the modeller associates with scenario ω, for ω∈Ω,andω∈Ωwω=1andg∈Gtwg=1∀t∈T. Let ωbe a given scenario in Ωgfor g∈G. Different types of models can be presented depending upon the type of recourse to consider, namely, simple, partial and complete recourse. Let us consider the minimization of the objective function expected value with complete recourse. In this
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 113 case, the stochastic version of program (1) has the following DEM, min QE= ω∈Ω wω(cωxω+aωyω) s.t. Axω+Byω=bω∀ω∈Ω (x,y)∈N xω∈{0,1}n,yω≥0∀ω∈Ω, (2) where cωand aωare the row vectors of the objective function coefficients, xωand yω are the vectors of the related variables and bωis the rhs vector for scenario ω,andN is the so-called feasible space to satisfy the non-anticipativity constraints for the x–and y–variables, such that v∈N={vω t|vω t=vω t∀ω∈Ωg,g∈G t,t∈T−},(3) where v=(x,y)andvω tis such that vω=(vω t,∀t∈T). Two approaches can be used to represent the constraints (3), namely, splitting variable and compact representations. The first approach has two types of formulations. One is so-called node-related (or scenario group related) representation. It requires to produce siblings of the variables that have nonzero elements in the constraints that belong to different stages. Another, so-called scenario-related representation, requires siblings of all variables in the model. In both cases, the non-anticipativity constraints must be explicitly added, but the second type preserves the model’s structure in a more amenable way for the approach considered in this work; its model is as follows, min QE= ω∈Ω wω(cωxω+aωyω) s.t. Axω+Byω=bω∀ω∈Ω vω t−vω t=0∀ω∈Ωg,g∈G t,t∈T− xω∈{0,1}n,yω≥0∀ω∈Ω. (4) The compact representation requires to model the relationships of the variables in more detail. For illustrative purposes, assume that the variables vector vω thas nonzero coefficients in the constraints related to the stages tand t+1, such that the deterministic model can be written as follows, min cx +ay s.t. A− txt−1+Atxt+B− tyt−1+Btyt=bt∀t∈T xt∈{0,1}n,yt≥0∀t∈T, (5)
114 On modelling planning under uncertainty in manufacturing where xtand ytare the vectors of the variables for stage tsuch that x=(xt∀∈T)and y=(yt∀∈T), ngives the dimension of the vectors xt,andA− t,At,B− tand Btare the related constraint matrices. By slightly abusing the notation, the stochastic version of the model can be expressed min QE= g∈G wg(cgxg+agyg) s.t. A− txγ(g)+Atxg+B− tyγ(g)+Btyg=bg∀g∈G t,t∈T xg∈{0,1}n,yg≥0∀g∈G, (6) where cgand agare the row vectors of the objective function coefficients, bgis the rhs vector, and xgand ygare the vectors of the variables for scenario group g,such that cg=cω t,ag=aω tand bg=bω twhere, in general, dω=(dω t∀t∈T), for ω∈Ωg,g∈G t,t∈T. 1.3 Mean-risk objective function The models that we have considered in the previous section aim to minimize the objective function expected value. However, there are some other approaches that additionally deal with the risk measures by also considering, e.g., semi-deviations [66], excess probabilities [76] and conditional value-at-risk [77] as we mentioned above. Those approaches are more amenable than the classical mean-variance schemes, mainly in the presence of 0−1 variables. Let φdenote a prescribed threshold for the excess probability,say,QP, such that QP=P(ω∈Ω:cωxω+aωyω>φ).(7) So, alternatively to min QE(2), the mean-risk function to minimize is as follows, QE+ηQP,(8) where ηis a positive weighting parameter. A more amenable expression of (8) for computational purposes, at least, can be min ω∈Ω wω(cωxω+aωyω+ηνω) s.t. cωxω+aωyω≤φ+Mνω∀ω∈Ω νω∈{0,1}∀ω∈Ω, (9) where νωis a 0−1 variable, such that its value is 1 if the objective function value for scenario ωis greater than threshold φand, otherwise, is 0, and Mis a parameter,
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 115 preferably, the smallest one which does not eliminate any feasible solution of the stochastic program under any scenario. 1.4 Branch-and-Bound bounding The instances of the mixed 0−1DEM (4) can have such large dimensions that the plain using of a state-of the-art optimization engine can make it unaffordable. Benders Decomposition schemes can be used as we mentioned above. Alternatively, we can execute a Branch-and-Bound (BB) scheme for optimizing the DEM, such that a Lagrangean Decomposition approach can be used at each BB node by dualizing the nonanticipativity constraints vω t−vω t=0∀ω∈Ωg,g∈G t,t∈T−,(10) see references above. In any case, heuristic Lagrangeans should be used. The Lagrangean model is as follows, min ω∈Ω wω(cωxω+aωyω+βνω)+ t∈T −,g∈Gt,ω∈Ωg μω t(vω t−vω t) s.t. cωxω+aωyω≤φ+Mνω∀ω∈Ω Axω+Byω=bω∀ω∈Ω 0≤xω≤1,0≤νω≤1,yω≥0∀ω∈Ω, (11) where μω t,∀ω∈Ωg,g∈G t,t∈T −denotes the row vector of the Lagrange multipliers associated with the non-anticipativity constraints (10). Notice that the number of Lagrange multipliers depends on the number of variables in the v–vector and the number of scenarios in each group. 1.5 Scenario clusters and Twin Node Families Alternatively to a Branch-and-Bound framework, we consider a variant of the Branchand-Fix Coordination (BFC) approach, such that it treats in a coordinate way the |Ω| independent models (12) that result from the relaxation of the constraints (10). min cωxω+aωyω+βνω s.t. cωxω+aωyω≤φ+Mνω Axω+Byω=bω xω∈{0,1}n,ν ω∈{0,1},yω≥0. (12)
116 On modelling planning under uncertainty in manufacturing Moreover, Lagrangeans can be used on the top. BFC is specially designed to coordinate the selection of the branching variable and branching node for each scenario-related Branch-and-Fix (BF) tree, such that the relaxed constraints (10) are satisfied when fixing the appropriate variables to either one or zero. The approach also coordinates and reinforces the scenario-related BF node pruning, the variable fixing and the objective function bounding of the subproblems attached to the nodes. The presentation of the scheme below is an extension of the scheme presented in [5]. See [3,4,6,8] for applications to the two-stage mixed 0−1 problem, where the first stage is only included by 0−1 variables, [37] for an application to the two-stage mixed 0−1 problem where the first stage is included by 0−1 variables and continuous variables and [7] for an application to the multistage pure 0−1 problem. For the presentation of the BFC approach, let Rωdenote the BF tree associated with scenario ω,Aωbe the set of active nodes in Rωfor ω∈Ω,Ithe set of indices of the variables in any vector xω t,and(xω t)ithe i-th variable in xω t, for t∈T,ω∈Ω,i∈I. Definition 4 Two variables, say, (xω t)iand (xω t)iare said to be common variables for the scenarios ωand ω,ifω, ω∈Ωg,g∈G t,forωω,t∈T −,i∈I. Notice that two common variables have nonzero elements in the non-anticipativity constraint related to a given scenario group. Definition 5 Any two nodes, say, a ∈A ωand a∈A ωare said to be twin nodes with respect to a given scenario group if the paths from their root nodes to each of them in their own BF trees Rωand Rω, respectively, either having not yet branched on/fixed their common variables, if any, or having the same 0−1value for their branched on/fixed their common variables (xω t)iand (xω t)i,forω, ω∈Ωg,g∈G t,t∈T−,i∈I. Definition 6 ATwin Node Family (TNF),say,Jfis a set of nodes such that any node is a twin node to all the other node members in the family, for f ∈F,whereFis the set of the families. Note: For practical reasons, all BF nodes belong to one TNF,atleast, even if its cardinality is one. Definition 7 Acandidate TNF is a TNF whose members have not yet branched on/fixed all their common variables. Definition 8 ATNF integer set is a set of TNFs where all x– and ν–variables take integer values, there is one node per each BF tree and the nonanticipativity constraints (xω t)i−(xω t)i=0are satisfied, ∀ω, ω∈Ωg,g∈G t,t∈T −,i∈I. Note: The cardinality of each TNF is one in any integer set. Let us consider the scenario tree and the BF trees shown in Figure 2, where xω h denotes a given variable subscripted hunder scenario ωand xhgives the generic notation for the variable. For illustrative purposes, let the branching ordering be x1,x2,...,x6.We can see that the first candidate TNF is J1, since the variables from stage 1 are common
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 117 variables to all nodes. Additionally, J2is a family that has already been branched on the same value of the common variable x1.Itisalsoacandidate TNF since the common variable x2has not been branched on (and, suppose that it has not been fixed either). Similarly, J3is another candidate TNF.However,J4is not a candidate TNF since all the common variables for their node members have been already branched on. The family J4is split into the families J5and J6to branch independently on the variables x3and x4, since the nodes 10 and 11 are twin nodes for these variables, while node 12 is not. Finally, note that J7and J8are also candidate TNFs, since the variable x4is not yet branched and, on the other hand, it is a common variable for the node members of those families. It is clear that the relaxation of the non-anticipativity constraints (10) is not required for all pairs of scenarios in order to gain computational efficiency. The number of scenarios to consider in a given model basically depends on the dimensions of the scenario related model (12). Definition 9 Ascenario cluster is a set of scenarios whose non-anticipativity constraints are explicitly considered in the model. The criterion for scenario clustering in the sets, say, Ω1,...,Ωq, where qis the number of scenario clusters, is instance dependent. However, we favour the approach that shows higher scenario clustering for greater number of scenario groups in common. In any case, notice that ΩpΩp=∅,p,p=1,...,q:ppand Ω=∪q p=1Ωp. The model to consider for scenario cluster p =1,...,qcan be expressed by the compact representation (13), where ωfor d∈G|T | is the unique scenario such that ω∈Ωdand, on the other hand, Gp={g∈G:ΩgΩp∅}. min d∈G|T | Gp wω g∈Nd cgxg+agyg+β ω∈Ωp wωνω s.t. g∈Nd cgxg+agyg≤φ+Mνω∀d∈G |T | Gp A− txγ(g)+Atxg+B− tyγ(g)+Btyg=bg∀g∈G tGp,t∈T xg∈{0,1}n,yg≥0,∀g∈G p νω∈{0,1}∀ω∈Ωp. (13) Remind that Ndgives the set of nodes in the ancestor path from leaf-node dto root node 1. Note: n≡|I|. The scenario cluster models (13) are linked by the non-anticipativity constraints: xgp−xgp=0 (14) ygp−ygp=0,(15) for p,p=1,...,q:pp,where gp∈G p,gp∈G pand gp=gp.
124 On modelling planning under uncertainty in manufacturing Objective Maximize the total net revenue, given by z2−z1,see below. Stage 1 (Strategic) Submodel z1= i∈I k∈Ki qk i0γk i0(16) subject to i∈I γ1 i0≤ N(17) γk−1 i0≥γk i0∀k∈K i\{1},i∈I (18) i∈I k∈Ki ak i0γk i0≤P0(19) j∈J\L αj≤ N(20) αj≤αg∀g∈Cj,j∈J (21) Njαj≤ i∈Ij βi j≤Njαj∀j∈E (22) βi j≤γ1 i0∀i∈I j,j∈J (23) j∈J/i∈Ij βi j≤Niγ1 i0∀i∈I (24) j∈R/i∈Ij βi j≤Ni∀i∈V (25) αj∈{0,1}∀j∈E (26) βi j∈{0,1}∀i∈I j,j∈E (27) γk i0∈{0,1}∀k∈K i,i∈I (28) Constraints (17) ensure that the number of plants in the supply chain will not exceed the allowed maximum. Constraints (18) ensure that the γ–variables are well defined. Constraints (19) take into account the investment budget. Constraints (20) restrict the number of end products for processing. Constraints (21) determine the production/supplying of the first tier components of any product selected. By considering the BoM requirements in the operation submodel, see below specifically constraints (39), it is easy to see the redundancy of (21). However, this type of
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 125 cuts reduces the linear programming (LP) solution space and, then, helps to tighten the model. Constraints (22) conditionally lower and upper limit the number of plants/vendors for each product/raw material. Constraints (23) restrict the processing of products to those plants that are in operation. Constraints (24) and (25) ensure that the number of products/raw materials for processing in plant/supplying from vendor i will not exceed the allowed maximum. We can observe that the rhs of (24) has been reinforced by multiplying it by γ1 io.On the other hand, enlarging the model by appending the variable upper bound βi j≤αj, i∈I j,j∈Eresults in a 0−1LP equivalent stronger model as well. However, given the potentially high number of β-variables, the appending should only be performed for violated cuts by the current LP solution. Stage 2 (Operation) Submodel Stage 2 submodel. Time period indexed profit function to maximize z2= t∈T j∈J i∈Ij m∈Mj pim jt yim jt − t∈T j∈E i∈Ij (ci jt xi jt +hi jt si jt)− − t∈T j∈J g∈Cj f∈Ig i∈Ij bfi gefji gt − i∈I k∈Ki\{1} t∈Ti qk it(γk it −γk i,t−1) (29) Stage 2 submodel. Time period indexed capacity expansion constraints γ1 i,t−1=γ1 it ∀i∈I,t∈T (30) γk i,t−1=γk it ∀k∈K i\{1},t∈T\T i,i∈I (31) γk i,t−1≤γk it ∀k∈K i\{1},t∈T i,i∈I (32) γk−1 it ≥γk it ∀k∈K i\{1},i∈I,t∈T (33) i∈I k∈Ki\{1} ak it(γk it −γk i,t−1)≤Pt∀t∈T (34) piγ1 i0≤ j∈J/i∈Ij oi jxi jt ≤ k∈Ki pk iγk it ∀i∈I,t∈T (35) Stage 2 submodel. Time period indexed operation constraints si j,t−1+xi jt =ρi jt +σi jt +si jt ∀i∈I j,j∈E,t∈T (36) Xi jβi j≤xi jt ≤Xi jβi j∀i∈I j,j∈E,t∈T (37)
126 On modelling planning under uncertainty in manufacturing Si jtβi j≤si jt ≤Si jβi j∀i∈I j,j∈E,t∈T (38) f∈Ig efji gt =Ngjxi jt ∀g∈Cj,i∈I j,j∈J,t∈T (39) i∈Ij yim jt ≤Dm jt ∀m∈M j,j∈J,t∈T (40) yim jt ≥0∀i∈I j,m∈M j,j∈J,t∈T (41) efji gt ≥0∀f∈I g,g∈Cj,i∈I j,j∈J,t∈T (42) where ρi jt ≡⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ ∈J/j∈C f∈I eif jt ,for j∈C 0,for j∈J\L and σi jt ≡⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ m∈Mj yim jt ,for j∈J 0,for j∈R The constraints have been divided into two blocks, namely, capacity expansion related constraints (30)-(35) and operation related constraints (36)-(42). Constraints (30) ensure that the plants are only open at time period t=0. Constraints (31) ensure that the capacity expansion of the plants will only occur at permitted time periods. Constraints (32) and (33) assure that the γ-variables are well defined. Constraints (34) take into account the capacity expansion budget. Constraints (35) limit the production from each plant to a conditional minimum, as well as to the maximum capacity given by the expansion plan. Constraints (36) are the stock balance equations for products and raw materials. Constraints (37) and (38) define the semi-continuous character of the production and stock variables. These constraints imply the non-negativity of the variables xi jt and si jt,∀i∈I j,j∈E,t∈T. Constraints (39) define the BoM requirements for the products. Constraints (40) ensure that the product shipment to the market sources will not exceed the related demand. The objective of the strategic SCM is to maximize the expected benefit over the scenarios, given the uncertainty in the production/supplying cost ci jt, product demand Dm jt and net profit pim jt . So, the uncertain parameters and all the variables have the superindex ωin the splitting variable representation for ω∈Ω, such that the following nonanticipativity constraints are satisfied,
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 127 αω j−αω j=0 (43) βiω j−βiω j=0 (44) γkω i0−γkω i0=0.(45) Let an instance with |I| =6plants,|Ki|=3 capacity levels each, |J| =12 products, where |L| =8 are subassemblies, |R|=12 raw materials, |V| =24 vendors, |Mj|=2 markets for each of the products, |T | =10 time periods and |Ω|=23 scenarios. The dimensions of DEM, compact representation are 69871 constraints, 56785 continuous variables and 895 0−1 variables. Given the large dimensions of the real-life instances, the plain use of state-of-the-art optimization engines cannot provide the solution in affordable computing time. So, we propose to use the Branch-and-Fix Coordination approach given in [3,5]. 3 Multi-Period Single Sourcing problem 3.1 Introduction In this section we deal with a modelling of a two-stage stochastic mixed 0−1 problem where the continuous variables only appear in the second stage, the socalled Multi Period Single Sourcing Problem (MPSSP) under uncertainty, where the objective function is included by the mean function and the weighted excess probability functional. Given a time horizon, a set of retailers and a set of facilities (e.g., production plants), the MPSSP is concerned with assigning each retailer to a unique facility at the beginning of the time horizon. The aim is to minimize the composite function of the expected assignment, inventory holding and backlogging costs and the weighted function of the probability of the excess cost with respect to a given target subject to the satisfaction of retailers’ demands and the production capacity constraints at the facilities. The assignment cost includes the production and distribution costs. The problem can be viewed as an assignment problem where the goodness of the retailers’ assignment can be measured against its performance along the time horizon. There are substantial differences between the procedures for solving the expected objective function minimization and the mean-risk functional minimization. See [9]. 3.2 Problem statement Consider a production/distribution network of a single product including a set of facilities and a set of retailers. Each facility can be interpreted as a production plant
128 On modelling planning under uncertainty in manufacturing with an associated warehouse. Each retailer needs to be served by (assigned to) a unique facility. The product demand and all costs along a given time horizon are unknown, but it is assumed that the uncertainty can be represented by a set of scenarios. Each production plant has a finite, known production capacity. We assume that each warehouse has sufficient capacity to be able to store the cumulative excess production of its corresponding production plant, even if this production plant produces to complete capacity in each time period. We assume that the product can only be stored at the facilities. Backlogging is also allowed at the facilities. The aim is to allocate the retailers to the facilities so that the objective function value is minimized. Sets: I,set of facilities. J,set of retailers. Deterministic parameter: bit,production capacity of facility iat time period t, for i∈I,t∈T. Uncertain parameters: Dω jt,product’s demand from retailer jat time period tunder scenario ω, for j∈J, t∈T,ω∈Ω. cω ij,assignment cost of retailer jto facility iunder scenario ω, consisting of the total production and distribution costs, for i∈I,j∈J,ω∈Ω. h+ω it ,unit inventory holding cost in facility iat time period tunder scenario ω, for i∈I, t∈T,ω∈Ω. h−ω it ,unit backlogging cost in facility iat time period tunder scenario ω, for i∈I,t∈T, ω∈Ω. Strategic variables: xij,0−1 variable such that its value is 1 if retailer jis assigned to facility iand 0 otherwise, for ∀i∈I,j∈J Tactical variables: s+ω it ,s−ω it ,product’s inventory and backlogging in facility iat (the end of) time period t under scenario ω, respectively, for i∈I,t∈T,ω∈Ω. 3.3 Mixed 0 − 1 DEM . Expected cost function minimization The following is a compact representation of the mixed 0−1DEM for the two-stage stochastic MPSSP with complete recourse to minimize the expected cost.
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 129 min QE= ω∈Ω wω i∈I j∈J cω ijxij + i∈I t∈T (h+ω it s+ω it +h−ω it s−ω it )(46) subject to i∈I xij =1∀j∈J (47) j∈J Dω jt xij +s+ω it +s−ω i,t−1≤bit +s+ω i,t−1+s−ω it ∀i∈I,t∈T,ω∈Ω(48) s+ω i0=s−ω i0=0∀i∈I,ω∈Ω(49) xij ∈{0,1}∀i∈I,j∈J (50) s+ω it ,s−ω it ≥0∀i∈I,t∈T,ω∈Ω.(51) The objective function (46) consists of the expected assignment, inventory holding and backlogging costs along the time horizon over the scenarios. Constraints (47), together with constraints (50), ensure that each retailer is assigned to exactly one facility. Constraints (48) ensure that the production capacity of the facilities is not violated. Notice that the model (46)–(51) is always feasible. We propose in [8] an equivalent formulation of the compact representation (46)–(51) based on splitting the assignment variables. In particular, we replace each variable xij by xω ij ∀w∈Ωand append to the model the so-called non-anticipativity constraints (52) to ensure that the assignments are not subordinated to any of the scenarios. xω ij −xω+1 ij =0∀i∈I,j∈J,ω∈Ω−{|Ω|}.(52) Let an instance with |I| =10 facilities, |J| =150 retailers, |T | =6 time periods and |Ω|=400 scenarios. The dimensions of DEM, compact representation are 24150 constraints, 48000 continuous variables and 1500 0−1 variables. See in [8] the specialization of the Branch-and-Fix Coordination approach used for minimizing the expected cost as well as the computational experience. The proposed approach outperform a state-of-the-art optimization engine as well as the approach based on the average scenario. 3.4 Mixed 0 − 1 DEM . Mean-risk function minimization The above model aims to minimize the objective function expected value. However, one of the approaches that in addition deals with the risk measure considers the excess probability functional [76] as we mentioned above.
130 On modelling planning under uncertainty in manufacturing Recall that φdenotes a prescribed threshold for the excess probability,say,QP,such that QP=P(ω∈Ω:cωxω+hωsω>φ).(53) where cωand hωare the row vectors of the objective function coefficients for the xand svariables, respectively, So, alternatively to min QE(46), we propose to minimize the mean-risk function QE+ηQP.(54) A more amenable expression of (54) for computational purposes at least, can be min QE+η ω∈Ω wωνω s.t. i∈I j∈J cω ijxij + i∈I t∈T (h+ω it s+ω it +h−ω it s−ω it )≤φ+Mνω∀ω∈Ω νω∈{0,1}∀ω∈Ω, (55) where η, νωand Mas above, see Section 1.3. Let the synthesized model of the splitting variable representation of the mixed 0−1 DEM min (55) subject to (47)–(51) be expressed ZIP =min ω∈Ω wωcωxω+hωsω+ηνω s.t. cωxω+hωsω≤φ+Mνω∀ω∈Ω i∈I xω ij =1∀j∈J,ω∈Ω Dωxω+Bsω=b∀ω∈Ω xω ij −xω+1 ij =0∀i∈I,j∈J,ω∈Ω−{|Ω|} sω 0=02m∀ω∈Ω xω∈{0,1}mn ∀ω∈Ω sω≥0r∀ω∈Ω νω∈{0,1}∀ω∈Ω, (56) where cωand hωare as above, Dωis the time indexed constraint matrix for the product’s demand from the retailers, Bis the time indexed constraint matrix (+1,−1,0) for the product’s inventory and backlogging, bis the rhs vector, xω=(xω ij)i∈I,j∈J gives the m×nvector of the 0−1 variables, Sωgives the r-vector for the continuous variables, where m=|I|,n=|J| and r=2m|T |, for ω∈Ω,Mand νare as above and Sω 0gives the vector for the continuous variables when t=0.
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 131 Consider an example with |I| =10 facilities, |J| =100 retailers, |T | =6 time periods and |Ω|=100 scenarios. The dimensions of DEM, compact representation are 6200 constraints, 12000 continuous variables and 1100 0−1 variables. Due to the type of objective function in model (56), the computational experience with plain use of a general state-of-art optimization engine does not give good results, nor the plain use of the Branch-and-Fix Coordination approach [5]. Moreover, the implementation of the heuristic algorithm so-called the Fix-and-Relax Coordination introduced in [9] provides better results in an affordable computing time. 4 Single level Production Planning and Raw Material Supplying under 4Uncertainty 4.1 Problem statement The planning of the production capacity utilization and the supplying of raw material is one of the most important managerial tactical responsibilities in manufacturing. In particular, the problem consists of deciding how much production and raw material supply, and how much product demand loss and backlogging can be expected at each period along a time horizon. The production capacity constraints, the product stock limitations, some logistic constraints related to the production lot sizing and the product demand requirements should be satisfied at a minimum cost. There is a vast amount of literature on the deterministic version of the problem. See the seminal paper of [91] for considering only continuous variables. See [16, 28, 60, 69, 81, 83, 94], among others, for considering lot sizing limitations and other logical constraints (and, then, considering 0−1 variables). But there are not too many papers on the stochastic version of the problem. However, very frequently the production decisions must be made in the presence of uncertainty in several important parameters, such as raw material and production cost, product demand and resource availability along a multi-stage time horizon. We present below a mixed 0−1 model for production planning and raw material supplying, where the uncertainty is treated via a scenario tree based scheme, such that the occurrence of the events is represented by a multi-stage scenario tree. In particular, the 0−1 variables as well as the continuous variables appear at any stage along the time horizon. The unit cost of the raw material supplying is not constant but it is decreasing while the supplying volume is increasing. This nonlinear separable function can be modelled via a function with linear segments.
132 On modelling planning under uncertainty in manufacturing 4.2 Complete recourse mixed 0 − 1 DEM The following is the notation for the sets and parameters used in the tactical production planning model. Sets: I,set of raw materials. Ij,set of raw materials required by product j, for j∈J. J,set of products. R,set of resources. Deterministic parameters: N,maximum number of products to be produced in a single time period. Xjt,Xj,minimum and maximum volume of product jthat can be produced at time period t, respectively, if any, for j∈J,t∈T. Sj,maximum volume of raw material or product jthat can be in stock at any time period, for j∈IJ. σj,fraction of the accumulated non-served demand that is lost. orj,unit capacity consumption of resource rby product j, for r∈R,j∈J. Nij,volume of raw material irequired by one unit of product j, for i∈I j,j∈J. hj,unit holding cost of raw material or product jat any time period, for j∈IJ. aj,unit demand backlog penalty for product j, for j∈J. ρj,unit lost demand penalty for product j,for j∈J. fj,fixed cost to be incurred for producing product jat any time period, for j∈J. di,delay time since the ordering of raw material iuntil its availability for processing, for i∈I. Uncertain parameters under scenario group g∈G: Og r,available capacity of resource rat time period t(g), for r∈R. Dg j,demand of product jat time period t(g), for j∈J. cg j,unit supplying cost of raw material j, for j∈I, and unit processing cost of product jat time period t(g), for j∈J. (cg ip,aip), pair of points (ordinate supplying cost, abscissa supplying volume) to define the supplying cost function of raw material iat time period t(g), where p=1,...,q is a given pair and qis the number of pairs.
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 133 Variables under scenario group g∈G: δg j,0−1 variable such that its value is 1 if product jis produced under scenario group g, and 0 otherwise, for j∈J. xg j,ordering volume of raw material jat (the end of) time period t(g), for j∈I,and production volume of product jat time period t(g), for j∈J. sg j,stock volume of raw material j, for j∈Iand product j, for j∈Jat (the end of) time period t(g). zg j,served demand of product jat time period t(g), for j∈J. yg j,lost demand of product jfrom time period t(g), for j∈J. bg j,demand backlog of product jfrom time period t(g), for j∈J. Raw material supplying cost function: Alternative 1 The cost function is modelled by using the special ordered sets of type 2, or S2 sets. These are sets of ordered continuous nonnegative variables, say, λg ip for each pair p=1,...,qof which no more than two members may be nonzero with the further condition that if there are many as two they must be adjacent, for g∈G,i∈I, see [14,15]. The formulation is as follows, cg ixg i≡ p=1,...,q cg ipλg ip ∀g∈G,i∈I xg i≡ p=1,...,q aipλg ip ∀g∈G,i∈I p=1,...,q λg ip =1∀g∈G,i∈I (57) Alternative 2 The cost function is modelled by using the 0−1 variables, say, λg ip for each pair p=1,...,qand the continuous variables xg ip, for g∈G,i∈I. The formulation is as follows, cg ixg i≡ p=1,...,q (cg ip −cg i,p−1)/(ag ip −ag i,p−1)xg ip ∀g∈G,i∈I where cg i0=0andag i0=0 xg i≡ p=1,...,q xg ip ∀g∈G,i∈I ag i1λg i2≤xg i1≤ag i1 (ag i2−ag i1)λg i3≤xg i2≤(ag i2−ag i1)λg i2 ... 0≤xg iq ≤(ag iq −ag i,q−1)λg iq (58)
140 On modelling planning under uncertainty in manufacturing 6 Stochastic Sequencing and Scheduling problem 6.1 Introduction Sequencing and Scheduling Problems (SSPs) arise in many practical circumstances when planning the utilization of a production/manufacturing system. Many problems are basically optimization problems having the following form: given a set of operations to be executed along a time horizon, find a schedule to minimize the value of a given objective function subject to various constraints. Typical elements are: limited availability of the resources, multiperiod operations, subsets of jobs with exclusivity constraints, precedence relationships in the execution of the operations, etc. See [6,7]. This type of problems can be formulated as 0−1 models and fall into the category of NP−hard problems. Traditional branch-and-bound methods have proved to be very inefficient to solve them. Instead, heuristic and meta-heuristic approaches have been found to obtain satisfactory solutions for special classes of this type of problems, such as problems with single period operations and special objective functions (e.g., makespan minimization). See [12, 44] for a survey and research potentials in project scheduling under uncertainty, among others. On the other hand, there is a vast amount of literature on the polyhedral analysis of the problem and, then, on tightening 0−1 models and facet defining inequalities identification for the deterministic version of the problem, see [93,94], among others. Application cases of the SSP considered in this paper can be found in investment planning, see [39], and production units maintenance planning, see [30], besides the proper application in production/manufacturing, see [31, 93, 94], among others. All of these works only consider the deterministic version of the problem. However, very frequently the resource availability as well as the resource consumption by the operations execution and, as a consequence, their execution cost are uncertain parameters. 6.2 Problem statement Consider a set of jobs, each of them comprises a set of operations to be executed along the given time horizon. Each operation has a time window for its execution. The operations must be executed during a given number of consecutive so-called production time periods without preemption. Some jobs are alternative in the sense that one and only one of these jobs can be executed. Let us call a class to a set of alternative jobs. If a job is executed then the operations of the other jobs that belong to the same class cannot be executed (i.e., they cannot be assigned). It is assumed that some operations have assigned a dedicated machine (or working station) for their execution. Let us say that the operations with the same dedicated
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 141 machine belong to the same type, such that the simultaneous execution of these operations is not allowed. A setup in a dedicated machine can be required between the consecutive execution of two operations. It is allowed that one operation can belong to more than one type. There are precedence relationships in the execution of the operations. They can be expressed by a directed acyclic graph, where the nodes are associated with the operations and the arcs refer to the existence of a direct precedence between the execution of the operations represented by the from-node and the to-node of the arcs. The precedences have the transitivity property. Two types of precedences are considered, such that a minimum number (type 1) and a maximum number (type 2) of time periods are required between the starting of the executions. Asetofresources with uncertain availability along the time horizon is considered. The operations’ execution can require resource consumption in each of its production periods. The resource amount to be utilized depends on several factors and it is also an uncertain parameter. Although the resource availability is uncertain at the planning time period, it is assumed to be known at the (beginning of the) period where the resource is required. However, the resource consumption by the operations execution is only known at the consumption time, what means that the occurrence of the resource consumption scenario at a given time period is not known in advance. The goal consists of determining the time period at which each operation will start its execution (i.e., assignment), if any, such that a set of constraints is satisfied along the scenario tree. The objective function to minimize consists of the expected execution cost of the operations over the scenarios. 6.3 Pure 0 − 1 DEM The following is additional notation for the sets and parameters to be used in the section. Sets: R,set of resources. I,set of operations. J,set of jobs. C,set of classes of jobs. Ti,set of feasible time periods to start the execution of operation i, for i∈I(Ti⊆T). Ij,set of operations included in job j, for j∈J(Ij⊆I). Jc,set of jobs that belong to class c, for c∈C(Jc⊆J). M,set of types of operations. Im,set of operations that belong to type m, for m∈M(Im⊆I).
142 On modelling planning under uncertainty in manufacturing A1(resp., A2), set of ordered pairs of operations with precedence relationship type 1 (resp., type 2). Deterministic parameters: ei, i,earliest and latest time periods for starting the execution of operation i, respectively, for i∈I.Note:ei, i∈T iand Ti⊆{ei,ei+1,..., i}. di,number of the so-called production time periods that are required for the execution of operation i, for i∈I.Note:t∈T iimplies that 1 ≤t≤|T|−di+1. dm,setup time between the ending and the starting of the execution of two operations that belong to type m, for m∈M. p1 ab and p2 ab,minimum and maximum number of time periods (so-called time lag) between the starting of the execution of the operations aand b, for (a,b)∈A 1 and (a,b)∈A 2, respectively. Uncertain parameters under scenario group g∈G: og rih,amount of resource rthat is required by the execution of operation iduring its hth production time period under scenario group g, for r∈R,h=1,2,...,di,i∈I. Og r,available capacity of resource rat time period t(g), for r∈R. cg i,execution cost of operation iat time period t(g), for i∈I. Among the different alternatives to model the problem, we use the step variable based formulation given in [18]. Strategic variables: yj,0−1 variable such that its value is 1 if job jis selected for execution, and 0 otherwise, ∀j∈J. Sequencing and scheduling variables: zg i,0−1 variable such that its value is 1 if operation istarts its execution by time period t(g) under scenario group g,and0otherwise,∀g∈G t,t∈T :ei≤t,i∈I. The execution time interval for operation iis t(g),t(g)+1,...,t(g)+di−1 for zg i=1 and zγ(g) i=0. The following is a compact representation of the DEM for the multi-stage stochastic problem with complete recourse.
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 143 Objective Determine the execution sequencing and scheduling of the operations in order to minimize the expected cost of the operations’ execution over the scenarios along a time horizon, subject to the constraints (86)– (96). It can be expressed min i∈I t∈Ti g∈Gt wgcg i(zg i−zγ(g) i).(85) Constraints j∈Jc yj=1∀c∈C(86) zg i=yj∀g∈G i,i∈I j,j∈J (87) zγ(g) i≤zg i∀g∈G t,t∈T i\{ei}(88) zγ(g) i=zg i∀g∈G t,t∈T\Ti:ei<t< i,i∈I (89) zg i=zg i∀g∈N g\{g},g∈G i,i∈I (90) i∈Im ρit(zg i−μitzg i)≤1∀m∈M,g∈G t,t∈T (91) where ρit ≡⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1,ei≤t< i+di+dm 0,otherwise μit ≡⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1,ei+di+dm≤t 0,otherwise g=Ng∩G t−di−dm zg a≥zg b∀g∈G t,t∈T b:t< a+p1 ab,(a,b)∈A 1(92) where g=Ng∩G t−p1 ab zg a≤zg b∀g∈N g∩G t+p2 ab ,g∈G t,t∈T a:t< b−p2 ab,(a,b)∈A 2 (93) i∈I k∈Fi og rih(zk i−αitzγ(k) i)≤Og r∀r∈R,g∈G t,t∈T (94) where Fi≡k∈N g:t(k)∈T i,t−di<t(k) αit =⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1,ei<t 0,otherwise h=t−t(k)+1
144 On modelling planning under uncertainty in manufacturing zg i∈{0,1}∀g∈G t,t∈T :ei≤t,i∈I (95) yj∈{0,1}∀j∈J.(96) Constraints (86) force the assignment (i.e., the execution) of one and only one job for each class. Constraints (87) force the execution of all operations that are required by the selected jobs under any scenario, and prevent the execution of the operations that are required by the jobs that have not been selected. Notice that it is enough that g∈G iin the domain of the constraints. Constraints (88) ensure that the value 0 for the variable zg iis propagated through the ancestor path from node gdown to node kfor t(k)=eiin the scenario tree, for t(g)∈T i\{ei}. The constraints also ensure that the value 1 for the variable zγ(g)is propagated through the subtree with root node γ(g) in the scenario tree. Constraints (89) avoid the operations starting their execution in non-feasible time periods, independently of the scenario being considered. Note: From a computational point of view, the constraints (89) are not included in the model and the variable zg i, g∈G t,t∈T\Ti:ei≤t< iis replaced with the variable zg i,g∈G τ,τ∈T iin any other constraint, where τ=max t∈T i:t<t. Constraints (90) formally state the propagation of the z-value to the scenario groups in the subtrees whose root nodes are the latest start of the operations’ execution. Note: From a computational point of view, the constraints (90) are not included in the model and the variable zg i,g∈N g\{g}is replaced with the variable zg i,g∈G iin any other constraint. Let us name configuration system to the constraint system (86)–(90) and (95)-(96). Constraints (91), jointly with the configuration system, prevent the assignment of more than one operation of a given type at the same time period. Notice that the difference zg i−zg iequals 1 (and, so, the assignment of operation iprevents the assignment of any other operation of the same type at time period t(g)) if operation istarts its execution in the time interval given by the periods t(g)−di−dm+1andt(g). Constraints (92) and (93) ensure that the precedence relationships types 1 and 2 are not violated, respectively. By constraints (92), if operation bstarts at time period t(g), then operation amust start p1 ab periods earlier, at least, under the given ancestor scenario group from Gt(g)−p1 ab , for (a,b)∈A 1. By constraints (93), if operation astarts at time period t(g), then operation bmust start p2 ab periods later, at most, under any successor scenario group from Gt(g)+p2 ab , for (a,b)∈A 2. Constraints (94), jointly with the configuration system, ensure that the consumption of the resources does not exceed their availability. The compact representation (85)–(96) can also be transformed into a splitting variable representation by replacing the y–andz–variables with their respective siblings, where yjis replaced with yω j∀ω∈Ωand zg iis replaced with zω it ∀ω∈Ωg, for t=t(g),
A. Alonso-Ayuso , L.F. Escudero and M.T. Ortu˜ no 145 so that there is a submodel for each scenario ω∈Ω. The non-anticipativity constraints (97)-(98) are appended to the new model. yω j−yω j=0∀ω, ω∈Ω:ωω,j∈J (97) zω it −zω it =0∀ω, ω∈Ωg:ωω,g∈G t,t∈T :ei≤t,i∈I.(98) Consider an example with |C|=20 classes, |J| =31 jobs, |I|=399 operations, |T | =7 time periods, |Ω|=128 and |G| =255 scenario groups. The dimensions of DEM, compact representation are 208170 constraints and 185015 0−1 variables. From a practical point of view, due to the large-scale of the problem and its combinatorial nature, it cannot be solved up to optimality in affordable computing time but for moderated size instances, mainly in the number of scenarios. So, efficient heuristic approaches should be used. We consider in [7] an heuristic based on a mixture of a Fix-and-Relax approach, see [28, 39], for providing good solutions to the scenario–related sequencing and scheduling problem, and a Branch-and-Fix Coordination scheme, see [3, 5], for coordinating the branching phase in the scenario cluster–related Branch-and-Fix trees, so that the constraints (97)–(98) are satisfied. The results reported in [7] for large-scale instances are very encouraging, outperforming a state-of-the-art optimization engine. 7 Conclusions We have presented some modelling schemes in supply chain management and production planning under uncertainty by using a sample set of problems. The uncertainty is represented by a scenario tree. All the problems lie within the complete recourse environment. In any case, the presence of 0−1 variables is very frequent, mainly, for modelling the either-or decisions and the operations assignment, sequencing and scheduling. Two approaches can be used depending basically upon the amount of information that is available on the uncertain parameters, namely, two-stage Stochastic Integer Programming (SIP) (where the continuous variables only appear in the second stage) and multi-stage SIP (where the continuous variables and the 0−1 variables appear at any stage). There are good exact solutions for the two-stage and good heuristic approaches for the multi-stage, but there are very few exact algorithms for large-scale multi-stage problems. In any case, the SIP discipline has been proved to be essential for modelling and solving real-life Supply Chain and production planning and assignment problems.
146 References [1] Ahmed, S. (2004). Mean-risk objectives in stochastic programming. Stochastic Programming E-Print Series, http://dochost.rz.hu-berlin.de/speps. [2] Ahmed, S., King, A.J. and Parija, G. (2003). A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. Journal of Global Optimization, 26, 3-24. [3] Alonso-Ayuso, A., Escudero, L.F., Gar´ ın, A., Ortu˜ no, M.T. and P´ erez, G. (2003). An approach for strategic supply chain planning based on stochastic 0−1 programming. Journal of Global Optimization, 26, 97-124. [4] Alonso-Ayuso, A., Escudero, L.F., Gar´ ın, A., Ortu˜ no, M.T. and P´ erez, G. (2005). On the product selection and plant dimensioning problem under uncertainty. Omega, 33, 307-318. [5] Alonso-Ayuso, A., Escudero, L.F. and Ortu˜ no, M.T. (2003). BFC, a Branch-and-Fix Coordination algorithmic framework for solving some types of stochastic pure and mixed 0−1 programs. European Journal of Operational Research, 151, 503-519. [6] Alonso-Ayuso, A., Escudero, L.F. and Ortu˜ no, M.T. (2005). Modelling production planning and scheduling under uncertainty. In S.W. Wallace and W.T. Ziemba, editors, Applications of Stochastic Programming. MPS-SIAM-Series in Optimization, 217-252. [7] Alonso-Ayuso, A., Escudero, L.F., Ortu˜ no, M.T. and Pizarro, C. (2007). On a Stochastic Sequencing and Scheduling Problem. Computers &Operations Research, 34, 2604-2624. [8] Alonso-Ayuso, A., Escudero, L.F., Pizarrro, C., Romeijn, H.E. and Romero Morales, D. (2006). On solving the multi-period single-sourcing problem under uncertainty. Computational Management Science, 3, 29-53. [9] Alonso-Ayuso, A., Escudero, L.F. and Pizarrro, C. (2007). On SIP algorithms for minimizing the mean-risk function in the Multi Period Single Source Problem under uncertainty. In the refereeing process. [10] Andrade, R., Lisser, A., Maculan, N. and Plateau, G. (2006). Enhancing a Branch-and-Bound algorithm for two-stage stochastic integer network design-based models. Management Science, 52, 1450-1455. [11] Anthony, R.N. (1965). Planning and control systems: A framework for analysis. Technical report, Harvard University, Graduate School of Business Administration, Cambridge, Ma, USA. [12] Baptiste, Ph., Le Pape, C. and Nuijten, W. (2001). Constraint-Based Scheduling. Kluwer Academic Publishers. [13] Baricelli, P., Lucas, C. and Mitra, G. (1996). A model for strategic planning under uncertainty. TOP, 4, 361-384. [14] Beale, E.M.L. and Forrest, J.J.H. (1976). Global optimization using special ordered sets. Mathematical Programming, 10, 52-69. [15] Beale, E.M.L. and Tomlin, J.A. (1970). Special facilities in a general mathematical programming system for nonconvex problems using ordered sets of variables. In J. Lawrence, editor. Operations Research’69. Tavistock Publishing, 447-454. [16] Belvaux, G. and Wolsey, L.A. (2001). Modelling practical lot sizing problems as mixed-integer programs. Management Science, 47, 993-1007. [17] Benders, J.F. (1962). Partitioning procedures for solving mixed variables programming problems. Numerische Mathematik, 4, 238-252. [18] Bertsimas, D. and Stock-Patterson, S. (1998). The air traffic flow management problem with enroute capacities. Operations Research, 46, 406-422. [19] Birge, J.R. (1985). Decomposition and partitioning methods for multi-stage stochastic linear programs. Operations Research, 33, 1089-1107.
147 [20] Birge, J.R. and Louveaux, F.V. (1997). Introduction to Stochastic Programming. Springer. [21] Bitran, G.R. and Tirupati, D. (1993). Hierarchical production planning. In A.H.G. Rinnooy-Kan S.C. Graves and P.H. Zipkin, editors. Logistics of Production and Inventory, 523-568. North-Holland. [22] Carøe, C.C. and Schultz, R. (1999). Dual decomposition in stochastic integer programming. Operations Research Letters, 24, 37-45. [23] Carøe, C.C. and Tind, J. (1998). L-shaped decomposition of two-stage stochastic programs with integer recourse. Mathematical Programming, 83, 451-464. [24] Cheung, R.K.M. and Powell, W.B. (1996). Models and algorithms for distribution problems with uncertain demands. Transportation Science, 39, 43-59. [25] Cohen, M.A. and Lee, H.L. (1989). Resource deployment analysis of global manufacturing and distribution networks. Journal of Manufacturing and Operations Management, 2, 81-104. [26] Cristobal, M.P., Escudero, L.F. and Monge, J.F. (2007). On Stochastic Dynamic Programming for solving large-scale tactical production planning problems. In the refereeing process. [27] Dert, C.K. (1998). A dynamic model for asset liability management for defined benefit pension funds. In W.T. Ziemba and J. Mulvey, editors. Worldwide Asset and Liability Modelling, 501-536. Cambridge University Press. [28] Dillenberger, Ch., Escudero, L.F. Wollensak, A. and Zhang, W. (1994). On practical resource allocation for production planning and scheduling with period overlapping setups. European Journal of Operational Research, 75, 275-286. [29] Eppen, G.D. Martin, R.K. and Schrage, L. (1989). A scenario approach to capacity planning. Operations Research, 37, 517-527. [30] Escudero, L.F. (1982). On maintenance scheduling of production units. European Journal of Operational Research, 9, 264-274. [31] Escudero, L.F. (1988). S3 sets. An extension of the Beale-Tomlin special ordered sets. Mathematical Programming, 42, 113-123. [32] Escudero, L.F. (1994). CMIT: A capacitated multi-level implosion tool for production planning. European Journal of Operational Research, 76, 511-528. [33] Escudero, L.F., de la Fuente, J.L., Garcia, C. and Prieto, F.J. (1999). A parallel computation approach for solving multi-stage stochastic network problems. Annals of Operations Research, 90, 131-160. [34] Escudero, L.F., Kamesam, P.V., King, A. and Wets, R.J.-B (1993). Production planning via scenario modelling. Annals of Operations Research, 43, 311-335. [35] Escudero, L.F., Galindo, E., G´ omez, E., Garc´ ıa, G. and Sabau, V. (1999). SCHUMANN, a modelling framework for supply chain management under uncertainty. European Journal of Operational Research, 119, 13-34. [36] Escudero, L.F., Gar´ ın, A., Merino, M. and P´ erez. G. (to appear 2007). On multistage Stochastic Integer Programming for incorporating logical constraints in asset and liability management under uncertainty. Computational Management Science. [37] Escudero, L.F., Gar´ ın, A., Merino, M. and P´ erez, G. (2007). On structuring Mortgage-Backed Securities porfolios under uncertainty. Annals of Operations Research, 152, 395-420. [38] Escudero, L.F., Quintana, F.J. and Salmer´ on, J. (1999). CORO, a modelling and an algorithmic framework for oil supply, transformation and distribution optimization under uncertainty. European Journal of Operational Research, 114, 638-656. [39] Escudero, L.F. and Salmer´ on, J. (2005). Fix-and-Relax Partitioning. An algorithmic framework for large-scale resource constrained project selection and scheduling. Annals of Operations Research, 140, 163-188. [40] Gassmann, H.I. (1990). MSLIP: A computer code for the multi-stage linear programming problem. Mathematical Programming, 47, 407-423.
148 [41] Graves, S.C., Rinnooy Kan, A.H.G. and Zipkin, E. (eds.) (1993). Logistics of Production and Inventory, North-Holland. [42] Groewe-Kuska, N., Kiwiel, K., Nowak, M.P., R¨ omisch, W. and Wegner, I. (2001). Power management in a hydro-thermal system under uncertainty by Lagrangeanrelaxation, In C. Greengard and A. Ruszczynski, editors. Decision making under uncertainty: Energy and Power, 39-70. [43] Hahn, C.K., Duplaga, E.A. and Hartley, J.L. (2000). Supply-chain synchronization: Lessons from hyundai motor company. Interfaces, 30, 32-45. [44] Hartmann, S. (1999). Project Scheduling under Limited Resources. Models, Methods and Applications. Springer. [45] Hemmecke, R. and Schultz, R. (2001). Decomposition methods for two-stage stochastic integer programs. In M. Gr¨ otschel, S.O. Krumke and J. Rambau, editors. Online Optimization of Large Scale Systems, 601-622. Springer. [46] Higle, J.L. and Sen, S. (1996). Stochastic Decomposition. A Statistical Method for Large-Scale Stochastic Linear Programming. Kluwer Academic Publishers. [47] Huang, K. and Ahmed, S. (2005). The value of multi-stage stochastic programming in capacity planning under uncertainty. Stochastic Programming E-Print Series, http://dochost.rz.huberlin.de/speps. [48] Kall, P. and Wallace, S.W. (1994). Stochastic Programming, John Wiley. [49] Karmarkar, U.S. (1989). Capacity loading and release planning with work in progress and lead times. Journal of Manufacturing and Operations Management, 2, 105-123. [50] Klein Haneveld, W.K. and Vlerk, M.H. van der (1999). Stochastic integer programming: General models and algorithms. Annals of Operations Research, 85, 39-57. [51] Klein Haneveld, W.K. and van der Vlerk, M.H. (2001). Optimizing electricity distribution using integer recourse models. In S. Uryasev and P.M. Pardalos, editors. Stochastic Optimization: Algorithms and Applications, 137-154. Kluwer Academic Publishers. [52] de Kok, A.G. and Graves, S.C. (eds.) (2003). Supply Chain Management: Design, Coordination and Operation. North-Holland. [53] Laporte, G. and Louveaux, F.V. (1993). The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13, 133-142. [54] Li, X. and Wang, Q. (2007). Coordination mechanisms of supply chain systems. European Journal of Operational Research, 179, 1-16. [55] Lucas, C., Mirhassani, S.A., Mitra, G. and Poojari, C.A. (2001). An application of lagrangian relaxation to a capacity planning problem under uncertainty. Journal of the Operational Research Society, 52, 1256-1266. [56] Lulli, G. and Sen, S. (2002). Stochastic batch-sizing problems: models and algorithms. In D.F. Woodruff, editor, Stochastic Integer Programming and Network Interdiction Models.Kluwer Academic Press. [57] Lulli, G. and Sen, S. (2004). A branch-and-price algorithm for multi-stage stochastic integer programming with application to stochastic batch-sizing problems. Management Science, 50, 786796. [58] Lulli, G. and Sen, S. (2006). A heuristic procedure for stochastic integer progrmas with complete recourse. European Journal of Operational Research, 171, 879-890. [59] Maatan, A., Schweigman, C., Ruijs, A. and van der Vlerk, M.H. (2002). Modelling farmers’ response to uncertain rainfall in burkina faso: A stochastic programming approach. Operations Research, 50, 399-414. [60] Miller, A.J. Nemhauser, G.L. and Savelsbergh, M.W.P. (2000). On capacitated lot-sizing and continuous 0−1 knapsack polyhedra. European Journal of Operational Research, 125, 298-315.
149 [61] MirHassani, S.A., Lucas, C., Mitra, G. and Poojari, C.A. (2000). Computational solution of capacity planning model under uncertainty. Parallel Computing Journal, 26, 511-538. [62] Mitra, G., Hajian, M. and Hai, I. (1977). A distributed processing algorithm for solving integer programs using a cluster of workstations. Parallel Computing Journal, 23, 733-753. [63] Ntaimo, L. and Sen, S. (2005). The million variable ’march’ for stochastic combinatorial optimization. Journal of Global Optimization, 32, 385-400. [64] Novak, M.P., Shultz, R. and Westphalen, M. (2002). Optimization of simultaneous power production and trading by stochastic integer programming. Technical report, Stochastic Programming E-Print Series. [65] N¨ urnberg, R. and R¨ omisch, W. (2002). A two-stage planning model for power scheduling in a hydrothermal system under uncertainty. Optimization and Engineering, 3, 355-378, 2002. [66] Ogryczak, W. and Ruszczynski, A. (1999). From stochastic dominance to mean-risk models: semideviations as risk measures. European Journal of Operational Research, 116, 33-50. [67] Parija, G., Ahmed, S. and King, A.J. (2004). On bridging the gap between stochastic integer programming and MIP solver strategies. INFORMS Journal on Computing, 16, 73-83. [68] Pinedo, M. (1995). Scheduling Theory, Algorithms and Systems. Prentice-Hall. [69] Pochet, Y. and Wolsey, L.A. (1991). Solving multi-item lot sizing problems using strong cutting planes. Management Science, 37, 53-67. [70] Rockafellar, R.T. and Uryasev, S. (2000). Optimization of Conditional Value-at-Risk. Journal of Risk, 2, 21-41. [71] Rockafellar, R.T. and Wets, R.J-B. (1991). Scenario and policy aggregation in optimisation under uncertainty. Mathematics of Operations Research, 16, 119-147. [72] R¨ omisch, W. and Schultz, R. (2001). Multi-stage stochastic integer programs: An introduction. In M. Gr¨ otschel, S.O. Krumke and J. Rambau, editors. Online Optimization of Large Scale Systems, 581-600. Springer. [73] Santoso, T., Ahmed, S., Goetschalckx, M. and Shapiro, A. (2005). A stochastic programming approach for supply network design under uncertainty. European Journal of Operational Research, 167, 96-115. [74] Schultz, R. (2003). Stochastic programming with integer variables. Mathematical Programming,Ser. B 97, 285-309. [75] Schultz, R., Nowak, M. and Westphalen, M. (2005). A stochastic integer Programming model for incorporating day-ahead trading of electricity into hydro-thermal unit commitment. Optimization and Engineering, 6, 163-176. [76] Schultz, R. and Tiedemann, S. (2004). Risk aversion via excess probabilities in stochastic programs with mixed-integer recourse. SIAM Journal on Optimization, 14, 115-138. [77] Schultz, R. and Tiedemann, S. (2006). Conditional Value-at-Risk in stochastic programs with mixed integer recourse. Mathematical Programming, Ser. B 105, 365-386. [78] Sen, S. and Sherali, H.D. (2006). Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Mathematical Programming, Ser. A 106, 203-223. [79] Sen, S. and Higle, J.L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixedinteger programming: Set convexification. Mathematical Programming, Ser. A 104, 1-20. [80] Sherali, H.D. and Zhu, X. (2006). On solving discrete two stage stochastic programs having mixedinteger first and second stage variables. Mathematical Programming, Ser. A 108, 597-611. [81] Shapiro, J.F. (1993). Mathematical programming models and methods for production planning and scheduling. In S.C. Graves, A.H.G. Rinnooy Kan and E. Zipkin, editors. Logistics of Production and Inventory, 371-443. North-Holland. [82] Shapiro, J.F. (2001). Modelling the Supply Chain. Duxbury.
156 Reference Poojari, C.A., Lucas, C. and Mitra, G. (2008). Robust solutions and risk measures for a supply chain planning problem under uncertainty. Journal of the Operational Research Society, 59, 2-12.
Francisco J. Prieto Universidad Carlos III de Madrid 1 Introduction This paper presents and discusses several formulation approaches to relevant production planning problems, with a particular emphasis on the treatment of uncertainty and risk within the corresponding frameworks. These are relevant and timely contributions, presented in a careful and detailed manner. While, as illustrated in the references for the paper, a significant amount of work has been carried out on the modelling of production and logistics problems for the deterministic case, a more limited effort has been devoted to the treatment of the uncertainty in these problems. In many practical applications within this context, issues related to the robustness of the solutions are very relevant; in a production world of small inventories and tight schedules, unforeseen disruptions can have a large impact on final results for any company. In this production context, robustness is possibly much more relevant than financial risk as a criterion to be modelled. Many improvements have taken place in recent years both regarding solvers for mixed integer programs and in approximation and decomposition algorithms, including several contributions from the authors ([6] or [10], for example). These improvements have brought the corresponding problems much closer to gaining widespread consideration within normal production planning processes. Perhaps in the near future it will be possible to see tools based on these models, and the corresponding solution techniques, incorporated as part of the most common decision support systems for production planning and business software in general. By giving a complete, clear and coherent presentation of these problems, this paper provides a significant contribution to this end. 2 Some comments The model descriptions and comments presented by the authors unavoidably give rise to many related and interesting issues. While they do not directly affect the contents of the paper, they may help to provide additional insights on these models and their practical application.
158 •One important issue that might merit some additional discussion is that of twostage vs. multi-stage formulations for the uncertainty. This modelling decision has implications on several aspects: the choice of a solution procedure, as any decomposition approach would depend significantly on the structure of the resulting problem; the uncertainty representation through the scenario trees: while its dependence structure would be in principle richer in the multi-stage setting, it would also require additional computational effort to generate and to handle; and the quality of the solution, as a better adapted set of values of the variables would potentially provide a more realistic solution. In the paper, the two-stage approach is preferred in most cases, except for the Production Planning and Raw Material Supplying problem and the Stochastic Sequencing and Scheduling problem. Nevertheless, in both these cases the temporal structure of the decisions is similar to that of the other problems, including both decisions taken now (without considering any future information) and future decisions adapted to the uncertainty, that can be reevaluated and optimized again later on. It is not clear that there is any significant advantage gained by not treating these problems also as two-stage ones. This approach would not seem to compromise much of the quality of the solutions, and might simplify (and homogenize) the modelling, while presenting computational advantages. •In most approaches to uncertainty planning in the literature, the uncertain values are associated to highly variable parameters, such as prices/costs or demand. This seems reasonable for everyday situations where the variability in the optimal decisions is mostly associated to these values, but in the production setting considered in the paper it could be argued that it would be as important to take into account the variability associated to unforeseen changes in capacity availability. For example, in model (10)–(22) both Ptand ¯ Nicould be treated as stochastic parameters, and similarly for ¯ Xi jin (23)–(36). This consideration raises an interesting issue: the treatment of low-probability situations within a scenario framework, such as those indicated above, as their treatment may have a significant impact on the quality of the solution. Using a MonteCarlo simulation analogy, there may be a problem with the variance of the estimates, as in principle only a few of these situations would be considered within the usual scenario generation approaches. Variance reduction techniques, such as importance sampling, could be helpful to improve the quality of the solutions in these cases. Additionally, scenario-tree reduction techniques based on moment-approximation may give results that are not particularly precise, as they are fitting a distribution for the input variables not knowing in advance which parts of that distribution are more relevant for the precise characterization of the distribution for the output variables.
159 Other approaches, such as dynamic scenario generation strategies, may be able to adapt to these situations and provide better answers in these settings (lowprobability but significant events). Of course, they would also have an impact on problem formulation and solution techniques, as the structure of the problem could be modified from iteration to iteration, and they may present significant difficulties in multi-stage settings. •Another question raised by the models in the paper is related to its prevalent use of an objective function based on a profit or cost criterion, possibly augmented with the inclusion of measures for excess probabilities associated with them. In manufacturing problems it is quite often the case that the goal is obtaining production/distribution schedules that are robust, that is, do not require much modification in the presence of perturbations. Also, in the uncertainty setting contemplated in the paper, other criteria related to quality become also relevant for the objective function. This raises the issue of the use of different objective functions/risk measures in this context. For example, and regarding the objective functions considered in several of the models, such as for example that of Section 2, it might be reasonable to include in them explicit measures of the delay in the satisfaction of the demand. In that particular case, a possible modification of the model might introduce variables covering separately the demand whose satisfaction has been delayed kperiods at time t, and updating them through an expanded conservation law similar to (30). In the case of the model in Section 6 it might be of interest to relax its formulation to allow for delays (that would otherwise be associated with infeasible solutions in the formulation presented in the paper), and to account for the number of periods that the execution extended beyond the latest time period allowed to complete it. This would require an extensive and complex modification of the model. Note that under uncertainty infeasibility becomes a more likely end result for formulations that are not sufficiently flexible to accommodate extreme outcomes in the values of the variables. The definition of robust solutions is also very relevant in this context. The objective function could include measures for the changes in solutions for different scenarios, and look for those that require smaller modifications between scenarios. For example, this could be done by considering the deterministic solutions for each scenario as references. Of course, a question open to debate would be the choice of an appropriate metric to compare these changes. •On a more specific topic, and regarding the models used in Sections 2 and 4 (Strategic Supply Chain Management and Single Level Production Planning), their treatment in an uncertain setting would suggest the possibility of giving explicit consideration within the model to futures and other instruments, to hedge some purchasing decisions against price (and availability) changes. In practice, this
160 would make particular sense at least regarding those raw materials that are traded in open markets (gas, fuel or electricity, for example). The additional terms required would not need to complicate the model significantly. It might be enough to introduce a portfolio of contracts with predefined time availabilities and costs, and zero-one variables related to the purchasing of the contracts and/or their usage within the model. That is, there would be additional suppliers with availabilities linked to stage-one decisions and having deterministic parameters in the model.
Andres Weintraub Dpto. de Ingenier´ ıa Industrial, Universidad de Chile, Santigao, Chile The issue of incorporating uncertainty explicitly is becoming increasingly central in modelling, driven largely by research sophistication, but also due to needs for more robust planning. There are several ways in which to incorporate uncertainty, and also to evaluate the need to actually do it explicitly. In this excellent paper by Alonso-Ayuso, Escudero and Ortuno,the authors present a summary, an integration of their important work in this field, in relation to modelling problems in manufacturing. Here they consider several levels of planning, going from strategic to tactical to operational decisions. Uncertainty is considered, depending on the level of decision in parameters dealing with demand, production costs, costs for raw materials, resource availability. Their approach to uncertainty is to consider tree scenarios, assigning probabilities to the scenarios, and finding deterministic equivalents with complete recourse. Given that the models they present deal with discrete decisions, all models have a MIP structure, and the approaches proposed are based on the non-anticipativity constraints to force same decisions for same scenarios up to any point in time. This can be represented by splitting variable or a compact representation, which allows to solve the problems in a decomposed form. I see here several main contributions. First, the form of representing uncertainty. While in theory probability distribution functions can be defined to represent uncertainty, in practice in most cases it is very difficult to determine such functions with accuracy. But planners can feel more comfortable thinking of scenarios, and assign probabilities to them. In some cases, there is a reasonably rigorous basis for establishing probabilities for scenarios. In other cases, the scenarios defined, and the probabilities are more like guesses. One open problem here could be analyzing the robustness of the decisions to variability in the probabilities of the scenarios. Considering the scenario approach, expressed in equation (2), there is ample experience to show that for large scale problems, which are usually the real ones, it is computationally infeasible to solve the problem as stated. Here comes the main contribution of the authors in their different works. They propose a successful way to decompose the problems, based on the non-anticipativity constraints. Perhaps here the
162 authors should help the reader by expanding Section 1.2, to clearly show how the two approaches work, the solution process, in particular for the compact representation. A small example might be of help here. It should be noted that the approaches proposed require a limited number of scenarios to be computationally tractable. While this condition on the number of scenarios in some cases can be a significant limitation, it can be considered to fall in line with the difficulties of planners of thinking of too many scenarios. The authors present several specific models for manufacturing. The models are not simple, can be considered similar to real, simplified cases, and uncertainty is incorporated into them where logic would indicate. Here we need to view two aspects I think. One is the way uncertainty is approached. The second are the models themselves. While these models need to be represented as they are, in some cases they are not easy to read. Maybe the relative complexity of the model formulation can overshadow the main result, which is the consideration of uncertainty. As for uncertainty, I believe the authors could present their results in a stronger way, by explaining more explicitly why they used a given approach for each problem. For example, in Section 2, why propose to use Branch and Fix Coordination, what are the results obtained? What is gained by the proposed approach as compared to more traditional approaches, including not considering uncertainty in an explicit form. So, in this case, there are two issues to consider, one is in relation to the improvement in robustness of the solutions when uncertainty is considered explicitly, and what is the cost due to this insurance. Note that these approaches by requiring to satisfy feasibility under all scenarios, have a component of being conservative. The second issue is related to the comparison of the proposed approaches with other alternatives. In Section 3.4, the Fix and Relax Coordination approach is presented. Again the paper I think would gain by explaining the method, why it was proposed and a short discussion of the results obtained through the use of this approach. The same comment applies to the approaches mentioned as solution methods in the other sections, and other problems presented. Basically the objective function is expressed in terms of expected value, and in some cases as excess probabilities. The latter adds another component to variability, trying to avoid solutions where the objective under certain scenarios are above a certain threshold value (this is used in Section 3.4, for example.). I believe a discussion is needed on why consider excess probability, why in specific problems, and what is gained by this consideration in Section 3.4 compared to Section 3.3.
163 I think the conclusion could be enriched by commenting in a general way on what are the conclusions of their work. How can they can link the different problems and models conceptually. These comments should be considered as a way to enrich the presentation of this work of very high quality, which opens a novel way to look at uncertainty and how to deal with it. It should be noted that the approaches presented in this paper are useful in other problem settings also.
Rejoinder First of all we would like to thank all the discussants for their comments and suggestions that we appreciate. To the remarks from prof. Monique Guignard On Question #1. The discussant addresses one of the most important issues in stochastic programming, namely, the generation of a set of enough representative scenarios and their probabilities. She offers a very comprehensive set of references that deal with the issue. We are not specialists on the matter and little more we can add, except to remark that there are approaches, see [26] as one example, that allow to generate thousands of scenarios to provide approximate solutions where state-of-the art optimization engines cannot provide any. On Question #2.Effectively, in most of the papers dealing with the computational aspects of algorithmic proposals, one finds statements related to one approach “outperforms” another. In deterministic environments it is an easy task, the approach with a better objective function value is “better” than the other one. In stochastic environments it is not so easy. One approach can be better than the other one for one scenario but worse and much worse for another one. Most of the approaches in stochastic programming deal with two-stage problems. For these approaches the methodology for deciding what approach outperforms some other is simple. Here, the result of the stochastic approach, say RP, that provides a solution for the first and the second variables, can be compared with the average scenario solution. The value of the first variables obtained by the average scenario approach is simulated for each scenario to consider, and the expected result of using the average solution, say EEV [20] is obtained. And, then, the values RP and EEV can be compared. A more difficult question is related to the value of the stochastic solution in multistage problems, and to what extend a solution “outperforms” another. An approach to the problem can be seen in Escudero et al. (2007), see below, where the definition of the bounds for the optimal value of the objective function is generalized to multistage stochastic problems. The definition of the parameters EVPI=RP-WS and VSS=EEV-RP for the two stage problems [20], where WS is the expected value of the scenarios treated in an independent form, is extended to the multistage stochastic problem. It is proved in Escudero et al. (2007) a similar chain of inequalities as for two-stage environments, with the lower and upper bounds depending substantially on the structure of the problem.