1-s2.0-S0307904X11005439-main

Two-stage fuzzy production planning expected value model and its approximation methodGuoqiang YuanFundamental Department,Hebei College of Finance,Baoding 071051,Chinaa r t i c l e i n f o Article history:Received 10July 2009Received in revised form 22August 2011Accepted 1September 2011Available online 8September 2011Keywords:Production planningTwo-stage fuzzy optimization Approximation method ConvergenceSimulated annealinga b s t r a c tThis work develops a novel two-stage fuzzy optimization method for solving the multi-product multi-period (MPMP)production planning problem,in which the market demands and some of the inventory costs are assumed to be uncertainty and characterized by fuzzy variables with known possibility distributions.Some basic properties about the MPMP pro-duction planning problem are discussed.Since the fuzzy market demands and inventory costs usually have infinite supports,the proposed two-stage fuzzy MPMP production plan-ning problem is an infinite-dimensional optimization problem that cannot be solved directly by conventional numerical solution methods.To overcome this difficulty,this paper adopts an approximation method (AM)to turn the original two-stage fuzzy MPMP production planning problem into a finite-dimensional optimization problem.The conver-gence about the AM is discussed to ensure the solution quality.After that,we design a heu-ristic algorithm,which combines the AM and simulated annealing (SA)algorithm,to solve the proposed two-stage fuzzy MPMP production planning problem.Finally,one real case study about a furniture manufacturing company is presented to illustrate the effectiveness and feasibility of the proposed modeling idea and designed algorithm.Ó2011Elsevier Inc.All rights reserved.1.IntroductionThe production planning is to decide what type of,and how much,product should be produced in a production period,it plays an important role in a manufacturing system.The decisions should be made under uncertainty,and uncertainty may be present as randomness and/or fuzziness in the practical production environment.Considering these uncertainties will result in more realistic production planning model.However,the inclusion of uncertainty in the production systems is a more dif-ficult task in terms of modeling and solution.The past four decades shows a growing interest in building models and algo-rithms for production planning problems such as the material requirements planning (MRP)models [1–3],the aggregate production planning (APP)models [4,5],the production inventory models [6–8],and many others [9–11].In order to handle probabilistic uncertainty in the production decision systems,some meaningful production planning stochastic models have been proposed in the literature.For example,Hodges and Moore [12]considered a product mix prob-lem with a number of linear resource constraints affecting the decision variables.Beale et al.[13]discussed the product mix problem with a stochastic demand depending on the random demands.Since the work of Dantzig [14],two-stage programs under stochastic environment have well extended and greatly developed in different disciplines,such as operations research,management science,control theory and artificial intelligence.In two-stage stochastic production problem,Gopalan and Anantharaman [15]examined the transient and steady-state characteristics of a two-stage transfer-line production system subject to inter-stage and end inspections and end buffer;Beraldi et al.[16]proposed a two-stage stochastic integer0307-904X/$-see front matter Ó2011Elsevier Inc.All rights reserved.doi:10.1016/j.apm.2011.09.001E-mail addresses:yggqq@ ,yggqq@2430G.Yuan/Applied Mathematical Modelling36(2012)2429–2445programming model for the integrated optimization of power production and trading which include a specific measure accounting for risk management;Sayarshad and Moghaddam[17]proposed a two-stage stochastic optimization formulation and solution procedure for optimizing thefleet size and freight car allocation under uncertainty demands.The readers who are interested in detailed discussion about two-stage stochastic programming may refer to the books[18,19].Since the pioneering work of Zadeh[20],possibility theory was being perfected and became a strong tool to deal with possibilistic uncertainty in fuzzy decision systems[21–23].Many researchers applied the theory successfully to fuzzy opti-mizations and effectively dealt with many practical problems in the past three decades[24–27].More importantly,possibil-ity theory also plays a key role for describing and processing fuzzy information in the realistic production decision systems. Therefore,fuzzy production planning problems attract many researchers0interests[28,29].Among them,Shih[28]applied three fuzzy linear programming models to solving transportation planning problem;Sharma et al.[29]presented a fuzzy goal programming model for handling fuzzy goal such as production and income of farmers in rural development planning. Although possibility theory is very popular and widely used in fuzzy community,the recent studies[30–33]show that it is credibility measure instead of possibility measure that plays the role of probability measure in fuzzy decision systems,and an axiomatic approach based on credibility measure,called credibility theory,was developed by the motivation of the fact [34].In addition,credibility theory has attracted much attention and been applied in manyfields to deal with incomplete and uncertain situation.For example,Zhang et al.[35]considered a fuzzy age-dependent replacement policy in which the life-times of components were treated as fuzzy variables,and the long-term expected cost per unit time was minimized;Liu[36] considered a new class of two-stage fuzzy programming problem in2005.Subsequently,he studied the basic properties of the proposed programming problems and discussed convergence of approximating a recourse function.Finally,he designed a heuristic algorithm to solve the proposed two-stage fuzzy programming problem;Lan et al.[37]presented a class of single-stage fuzzy production planning problem with credibility objective.However in contrast to previous stochastic and fuzzy production planning problem,credibility theory and two-stage fuzzy optimization method[36]to production planning prob-lems have not been studied extensively in the literature.The purpose of this paper is to apply credibility theory and two-stage fuzzy programming theory to practical production planning problem and presents a new class of two-stage fuzzy MPMP production planning expected value model.Besides, some basic properties about the proposed production planning problem are discussed in this paper.The two-stage optimi-zation methods were also used in the literature by a number of researchers.For example,Bakir and Byrne[38]considered an multi-product multi-period production planning model with stochastic demand.Subsequently,they developed a new de-mand stochastic linear programming model based mainly on the theoretical presentation of two-stage deterministic equiv-alents.In this paper,motivated by two-stage stochastic optimization[18],we define two-stage optimization using credibility measure instead of probability measure for our MPMP production planning problem.The proposed production planning problem in this paper is more general than[38],in which the market demands and some of the inventory costs are assumed to be uncertainty and characterized by fuzzy variables with known possibility distributions.Since the fuzzy market demands and fuzzy inventory costs usually have infinite supports,the proposed two-stage fuzzy production planning problem belongs to an infinite-dimensional optimization problem that cannot be solved directly.To overcome this difficulty,this paper con-siders an approximation method(AM)[39]for the original two-stage fuzzy MPMP production planning problem,and turns it to afinite-dimensional optimization problem.The convergence of the AM is also discussed in this paper.Since the approx-imating MPMP production planning problem is neither linear nor convex,conventional optimization algorithms cannot be applied in this paper.Therefore,we will design a heuristic algorithm,which combines the AM and SA algorithm,to solve the proposed two-stage fuzzy MPMP production planning problem.To demonstrate the practical relevance of our research,we design a furniture manufacturing problem as afive-productfive-period production planning problem in this paper.The rest of this paper is organized as follows.Firstly,we will recall some basic concepts in Section2,and then propose a new type of two-stage fuzzy MPMP production planning expected value model in Section3.Subsequently,some basic prop-erties about the two-stage fuzzy MPMP production planning problem are discussed in Section4.In Section5,we employ the AM to the expected value function of two-stage fuzzy MPMP production planning problem,and deal with the convergence of AM.The convergent result facilitates us to incorporate AM and SA algorithm to solve the proposed MPMP production plan-ning problem in Section5.To apply the proposed approach to a practical MPMP production planning problem,a real case study about a furniture manufacturing company is given in Section6to illustrate the feasibility and effectiveness of the de-signed heuristic algorithm.Section7summarizes the main results in this paper and points out our future research.2.PreliminariesThe concept of fuzzy set was initiated by Zadeh[40]via membership function in1965.In order to measure a fuzzy event, Zadeh[20]proposed the concept of possibility measure in1978.Although possibility measure has been widely used,it has no self-duality property.However,a self-dual measure is absolutely needed in both theory and practice.In order to define a self-dual measure,Liu and Liu[30]presented the concept of credibility measure in2002.Based on credibility measure,an axiomatic approach,called credibility theory[34,41]was studied extensively.Subsequently,wefirst recall some basic con-cepts in the following section.Given a universe C;PðCÞis the power set of C,and Pos is a set function define on PðCÞ.The set function Pos is called a possibility measure[23,42]if it satisfies the following conditions:Pos (1)Pos ð;Þ¼0,and Pos ðC Þ¼1.Pos (2)Pos S i 2I A i ÀÁ¼sup i 2I Pos ðA i Þfor any subclass f A i j i 2I g of PðC Þ,where I is an arbitrary index set.Based on possibility measure,a self-dual set function,called credibility measure Cr,is proposed by Liu and Liu [30].If the triplet ðC ;PðC Þ;Pos Þbe a possibility space and for any set A in PðC Þ,The credibility measure of the set A is defined byCr ðA Þ¼121þPos ðA ÞÀPos ðA c ÞÀÁ;where A c is the complement of A .Credibility measure has the following properties:Cr (1)Cr ð;Þ¼0,and Cr ðC Þ¼1;Cr (2)Monotonicity:Cr ðA Þ6Cr ðB Þwhenever A ;B 2PðC Þand A &B ;Cr (3)Self-duality:Cr ðA ÞþCr ðA c Þ¼1for all A 2PðC Þ,andCr (4)Subadditivity:Cr ðA [B Þ6Cr ðA ÞþCr ðB Þfor any A ;B 2PðC Þ.The triplet ðC ;PðC Þ;Cr Þis called a credibility space [41].Example 1.Let C ¼f c 1;c 2;c 3;c 4;c 5;c 6g .Define a set function Pos on PðC Þas follows:Pos f c 1g ¼0:2;Pos f c 2g ¼0:7;Pos f c 3g ¼0:6;Pos f c 4g ¼1;Pos f c 5g ¼0:5;Pos f c 6g ¼0:8and for any other set A 2PðC Þ,Pos ðA Þ¼max c i2APos f c i g .Then ðC ;PðC Þ;Pos Þis a possibility space.Calculate the possibility andcredibility of the fuzzy event f c 1;c 3;c 6g .The possibility and credibility of f c 1;c 3;c 6g can be calculated as follows:Pos f c 1;c 3;c 6g ¼max f Pos f c 1g ;Pos f c 3g ;Pos f c 6gg ¼max f 0:2;0:6;0:8g ¼0:8and Cr f c 1;c 3;c 6g ¼1ð1þPos f c 1;c 3;c 6g ÀPos f c 2;c 4;c 5gÞ¼0:4.In the following section,we will mainly introduce some basic concepts,which contain fuzzy vector,independence,cred-ibility distribution and expected value operator of the fuzzy variable in credibility theory.If the triplet ðC ;PðC Þ;Cr Þbe a credibility space and n ¼ðn 1;n 2;...n n Þis a function from C to the space R n ,then it is called a fuzzy vector.As n ¼1,it is called a fuzzy variable.The fuzzy variables n 1;n 2;...;n n defined on a credibility space ðC ;PðC Þ;Cr Þare said to be mutually independent [43]ifCr f c j n 1ðc Þ2B 1;n 2ðc Þ2B 2;...;n n ðc Þ2B n g ¼min 16i 6nCr f c j n i ðc Þ2B i gfor any subsets B 1;B 2;...;B n of R .On the other hand,if n is a fuzzy variable defined on a possibility space ðC ;PðC Þ;Pos Þ,then the credibility distribution of n is defined byG n ðr Þ¼Cr f c 2C j n ðc ÞP r g ;r 2R :A sequence f n n g of m -ary fuzzy vectors is said to converge uniformly [39]to an m -ary fuzzy vector n on C ,if for any given e >0,there is a positive integer N such that for all c 2C ,k n n ðc ÞÀn ðc Þk <e ;whenever m P N ,where k Ák is the Euclidean norm on R m .Let n be an m -ary fuzzy vector.The support of the fuzzy vector n ,denoted by N ,is defined as the closure of the set fðt 1;t 2;...;t m Þ2R m j l n ðt 1;t 2;...;t m Þ>0g ,it is the smallest closed subset of R m such that Cr f c j n ðc Þ2N g ¼1.An m -ary fuzzy vector n is said to be bounded if its support N is a bounded subset of R m .Example 2.Let n be a triangular fuzzy variable ðÀ1;2;3Þwith the following possibility distribution functionl n ðt Þ¼t þ13;À16t <2;3Àt ;26t <3;0;otherwise :8><>:Calculate the credibility distribution function of n .For any r 2R ,by definition of credibility distribution,one hasG n ðr Þ¼Cr f n P r g ¼12ð1þPos f n P r g ÀPos f n <r gÞ¼121þsup t P r l n ðt ÞÀsup t <r l n ðt Þ¼1;r <À1;5Àr;À16r <2;3Àr ;26r <3;0;otherwise :8>>><>>>:G.Yuan /Applied Mathematical Modelling 36(2012)2429–24452431Based on credibility measure,Liu and Liu[30]defined the expected value operator of a fuzzy variable.If n is a fuzzy var-iable defined on a credibility spaceðC;PðCÞ;CrÞ,then the expected value of n isE½n ¼Z10Cr f n P r g d rÀZ0À1Cr f n6r g d r;provided that at least one of the two integrals isfinite.Moreover,ifmaxZ10Cr f n P r g d r;Z0À1Cr f n6r g d r&'<1;then the expected value of n is said to befinite.Particularly,if n is a discrete fuzzy variable with the following possibility distribution functionl n ðxÞ¼l1if x¼a1;l2if x¼a2;......lnif x¼a n:8>>>><>>>>:Without any loss of generality,we assume that a16a26ÁÁÁ6a n,then the expected value becomes the following form:E½n ¼X ni¼1pia i;where the weights p0is are determined byp i ¼1maxij¼1ljÀmaxiÀ1j¼0ljþ1maxnj¼iljÀmaxnþ1j¼iþ1lj;ð1Þðl0¼0;l nþ1¼0Þfor i¼1;2;...;n,and satisfy the following constraintsp i P0;andX ni¼1pi¼maxni¼1li¼1:Example3.Let n be a triangular fuzzy variable defined in Example2.Calculate the expected value E½n of fuzzy variable n.By the definition of credibility distribution in Example2,for any r P0,we haveCr f n P r g¼5Àr;06r<2; 3Àr;26r<3; 0;otherwise 8><>:and for any r60,Cr f n6r g¼rþ1;À16r<0; 0;otherwise: (By the definition of the expected value,one hasE½n ¼Z10Cr f n P r g d rÀZ0À1Cr f n6r g d r¼Z25Àr6d rþZ323Àr2d rÀZ0À1rþ16d r¼32:For the recent books about the development of credibility theory,the readers may consult Liu and Wang[31]and Liu [34,44].3.Problem formulation3.1.Two-stage fuzzy optimization developmentIn this section,based on credibility theory,we will give a brief introduction to two-stage fuzzy programming or fuzzy programming with recourse(FPR).The reader who is interested in detailed discussion on this issue may refer to[36].To formulate an FPR problem,we start from the following underlying optimization problem:min c T xþq TðcÞy;s:t:Ax¼b;TðcÞxþWðcÞy¼hðcÞ;x P0;y P0:ð2Þ2432G.Yuan/Applied Mathematical Modelling36(2012)2429–2445Then assume that some components of qðcÞ;TðcÞ;WðcÞand hðcÞare fuzzy variables defined on a possibility space ðC;PðCÞ;PosÞ,and the decision–observation scheme is the followingdecision on x,observation of fuzzy event c,decision on y.According to this scheme,we present an FPR problem,in which there are two optimization problems to be solved.First-stage decision x is taken in the presence of uncertainty about future realization of n.In the second-stage,the actual value of n becomes known and some corrective actions or recourse decisions y can be taken.The second-stage problem,or recourse problem is formulated by assuming x and c to befixed,and is as followsmin q TðcÞy;s:t:TðcÞxþWðcÞy¼hðcÞ;y P0:ð3ÞBased on the notations above,an expectation-based two-stage fuzzy programming model is formulated as follows min c T xþE n½min q TðcÞy ;s:t:Ax¼b;TðcÞxþWðcÞy¼hðcÞ;x P0;y P0:ð4ÞIn the problem(4),thefirst-stage decision is represented by the n1Â1vector x.Corresponding to x are thefirst-stage vectors and matrices c;b and A of sizes n1Â1;m1Â1and m1Ân1,respectively.In the second-stage,a number of fuzzy events c2C may realize.For a given realization c,the second-stage problem data qðcÞ;TðcÞ;WðcÞand hðcÞbecome known,where qðcÞis n2Â1,TðcÞis m2Ân1;WðcÞis m2Ân2,and hðcÞis m2Â1.Each component of q;T;W,and h is thus a possible fuzzy var-iable.Let T iÁðcÞbe the i th row of TðcÞ,and W iÁðcÞbe the i th row of WðcÞ.Piecing together the fuzzy components of the second-stage data,we obtain a vector nðcÞwith potentially up to n2þm2þðm2Ân1Þþðm2Ân2Þcomponents.In[36],Liu have pointed out that the calculation of the expected value of the objective function in problem(4)is com-pletely different from that of the expected objective in stochastic programming model.Therefore,the solution methods developed for stochastic programming problems cannot be applied to the two-stage fuzzy programming ones.In order to avoid getting stuck at a local optimal solution,a heuristic algorithm,which incorporates fuzzy simulations,neural network and genetic algorithm,was designed to solve the two-stage fuzzy programming problems(4).3.2.The formulation of two-stage fuzzy MPMP production planning problemIn this section,based on credibility theory and two-stage fuzzy optimization method[36],we will construct the formu-lation of two-stage fuzzy MPMP production planning expected value model.The characteristic of this manufacturing system can be summarized as follows,which was also considered by Bakir and Byrne[38]in stochastic decision system.There are N types of products that are produced in this manufacturing system,and the decision of production levels to meet market demand with the minimum cost must be taken for T periods.The demand for each product in each period is not known with certainty and is characterized by a fuzzy variable with known possibility distribution.The profit and cost coefficients that are used in the model objective function consist of net production profit,inventory carrying and shortage costs.Some of the cost coefficients are not known exactly and assumed to be represented by fuzzy variables with known possibility distributions.The manufacturing system is assumed to be aflow type but not a pure one.There are K machine centers in the system,and each center is provided with one machine.All products trace the same route,and may skip some machine centers.A station is not to be visited more than once.The transfer times of parts between stations are negligible.The process times of each machine center are supposed to be deterministic.The setup times for each product in each machine center are included in the process times.In addition,we will adopt the following notations in the rest of this section.Notationsx it the amount of product i to be produced in period tc it the unit net production profit or revenue of product i in period tIþit the amount of positive inventories of product i at the end of period tIÀit the amount of negative inventories or shortages of product i at the end of period tG.Yuan/Applied Mathematical Modelling36(2012)2429–24452433qþit the unit cost of positive inventories of product i in the period tqÀit the unit cost of negative inventories or shortages of product i in the period ta ik the process time of product i on the machine center kd it the market demand for the i th product in t th periodMC kt the capacity of machine center k in period tA the technical identity matrixW the recourse identity matrixIn this paper,we will present a new class of two-stage fuzzy MPMP production planning problem,in which there are two optimization problems to be solved.Thefirst-stage decision variable x it which represents the amount of product i to be produced in period t must be taken before outcome of fuzzy event c.Here the outcome of fuzzy event refers to the realizations of the fuzzy market demands as well as the fuzzy inventory costs.In the second-stage,the fuzzy market de-mands and fuzzy inventory costs become known.As a consequence,the second-stage decision variables Iþit and IÀitshouldbe taken.According to this scheme,we will present an N-product T-period two-stage production planning problem in fuzzy envi-ronment.Then two-stage fuzzy MPMP production planning model is built asmax Z¼X Tt¼1X Ni¼1c it x it"#ÀE nX Tt¼1X Ni¼1Q itðx it;nðcÞÞ"#;s:t:X Ni¼1a ik x it6MC kt;x it P0;i¼1;2;...;N;t¼1;2;...;T;k¼1;2;...;K;ð5Þwhere for all t and i,Q itðx it;nðcÞÞ¼min q itðcÞI it;s:t:WI it¼Ax itþWI itÀ1Àd itðcÞ;I it¼Iþit ÀIÀit;qitðcÞ¼qþitðcÞÀqÀitðcÞ;Iþit P0;IÀitP0;qþitðcÞP0;qÀitðcÞP0;i¼1;2;...;N;t¼1;2;...;Tð6Þand the fuzzy vector nðcÞis obtained by piecing together the fuzzy components of the second-stage problem dataqþitðcÞ;qÀitðcÞand d itðcÞin problem(6).Obviously,for any i and t,we have IþitÂIÀit¼0in the proposed two-stage fuzzy MPMP production planning model.The solution of the model involves deciding what products should be produced and how much of each product to produce.The inventory at the end of period t is available for withdrawal by the next period,and provides the linkage between the periods of the multi-period model.There is no relation between the shortages in periods t and tÀ1. That is,backlogging is not allowed in problem(6).4.Properties of fuzzy MPMP production planning problemThe intent of this section is to deal with some basic properties of the two-stage fuzzy MPMP production planning prob-lem.For convenience,we will denote c Tt¼ðc1t;c2t;...;c NtÞ,ðQ tðx t;nðcÞÞÞT¼ðQ1tðx1t;nðcÞÞ;Q2tðx2t;nðcÞÞ;...;Q N tðx Nt;nðcÞÞÞand similarly forða kÞT;ðq tðcÞÞT,ðI tÞT;ðx tÞT,andðd tðcÞÞT in the rest of this section.Then the above two-stage fuzzy MPMP produc-tion planning problems(5)and(6)can be rewritten asmax Z¼X Tt¼1c Ttx tÀE nX Tt¼1Q t x t;nðcÞðÞ"#;s:t:a Tkx t6MC kt;x t P0;t¼1;2;...;T;k¼1;2;...;K;ð7Þwhere for all t,2434G.Yuan/Applied Mathematical Modelling36(2012)2429–2445Q t ðx t ;n ðc ÞÞ¼minq T t ðc ÞI t ;s :t :WI t ¼Ax t þWI t À1Àd t ðc Þ;I t ¼I þt ÀI Àt ;q t ðc Þ¼q þt ðc ÞÀq Àt ðc Þ;I þt P 0;I Àt P 0;q þt ðc ÞP 0;q Àt ðc ÞP 0;t ¼1;2;...;T :ð8ÞSuppose that the decision vector x t in this two-stage fuzzy MPMP production planning problem has to satisfy the follow-ing deterministic constraints:a T k x t 6MC kt ;x t P 0:Now we want to speak about the solution of fuzzy production planning problem (8),it is necessary to introduce addi-tional constraint on x t .Let K be the set of all those x t vectors for which problem (8)has a feasible solution for almost everypossibly realized fuzzy event c .Then K can be expressed asK ¼f x t j x t 2R N þ;Cr f c j Q t ðx t ;n ðc ÞÞ<1g ¼1g ;where n ðc Þis the fuzzy vector obtained by piecing together the fuzzy market demands and some of fuzzy inventory costs infuzzy production planning problem (8).The function Q t ðx t ;n ðc ÞÞis the optimal value of the fuzzy production planning prob-lem (8)at fixed x t and c ,and is usually called second-stage value function in fuzzy programming with recourse [36].Butwhen the Ax t þWI t À1P d t ðc Þ,the second-stage value function Q t ðx t ;n ðc ÞÞ¼min ðq þt ÞT ðc ÞI þt ;on the other hand,when theAx t þWI t À1<d t ðc Þ,the second-stage value function Q t ðx t ;n ðc ÞÞ¼min ðq Àt ÞT ðc ÞI Àt .So the fuzzy production planning problem (8)has always optimal value at each t ,we have K ¼R N þin finally.Proposition 1.The second-stage value function Q t ðx t ;n ðc ÞÞin the two-stage fuzzy MPMP production planning problem (8)has the following properties:(1)Q t ðx t ;n ðc ÞÞis a convex function with respect to d t ðc Þ;(2)Q t ðx t ;n ðc ÞÞis a concave function with respect to q t ðc Þ;(3)Q t ðx t ;n ðc ÞÞis a convex function almost sure with respect tox t 2K .Proof.We first prove the assertion (1).Let ðI 1t ÞÃand ðI 2t ÞÃbe the optimal solutions of the following second-stage program-ming problemQ t ðx t ;n ðc ÞÞ¼minI tq T t I t ;s :t :WI t ¼Ax t þWI t À1Àd t ðc Þ;I t ¼I þt ÀI Àt ;q t ¼q þt Àq Àt ;I þt P 0;I Àt P 0;q þt P 0;q Àt P 0;t ¼1;2;...;Tð9Þfor d t ¼d 1t ¼d t ðc 1Þand d t ¼d 2t ¼d t ðc 2Þ.Then,for any k 2ð0;1Þ;k ðI 1t ÞÃþð1Àk ÞðI 2t ÞÃis a feasible solution of problem (9)ford t ¼d k t with d k t ¼k d 1t þð1Àk Þd 2t .Let ðI k t ÞÃbe an optimal solution of problem (9)for d t ¼d k t .Then we haveQ t ðx t ;d k t Þ¼q T t ðI k t ÞÃ6q T t ðk ðI 1t ÞÃþð1Àk ÞðI 2t ÞÃÞ¼k q T t ðI 1t ÞÃþð1Àk Þq T t ðI 2t Þük Q t ðx t ;d 1t Þþð1Àk ÞQ t ðx t ;d 2t Þ;which verifies the first assertion.We now prove the second assertion.Let ðI 1t ÞÃand ðI 2t ÞÃbe the optimal solutions of the following second-stage programming problemQ t ðx t ;n ðc ÞÞ¼minI tq T t ðc ÞI t ;s :t :WI t ¼Ax t þWI t À1Àd t ;I t ¼I þt ÀI Àt ;q t ðc Þ¼q þt ðc ÞÀq Àt ðc Þ;I þtP 0;I ÀtP 0;q þt ðc ÞP 0;q Àt ðc ÞP 0;t ¼1;2;...;T ;ð10Þfor q t ¼q 1t ¼q t ðc 1Þand q t ¼q 2t ¼q t ðc 2Þ.Let q t ¼q k t ¼k q 1t þð1Àk Þq 2t for k 2ð0;1Þ.Then for any feasible solution I t of problem(10)for q t ¼q k t ,it is also the feasible solution of problem (10)for q t ¼q 1t and q t ¼q 2t .Hence,we haveG.Yuan /Applied Mathematical Modelling 36(2012)2429–24452435。