On solving stochastic production planning problems via scenario modelling

Summary Linear Porgramming models for stochastic planning problems and a methodology for solving them are proposed. A production planning problem with uncertainty in demand is used as a test case, but the methodology presented here is applicable to other types of problems as well. In these models, uncertainty in demand is characterized via scenarios. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield an implementable non-anticipative policy. Such an approach makes it possible to model correlated and nonstationary demand as well as a variety of recourse decision types. For computational purposes, two alternative representations are proposed. A compact approach that is suitable for the Simplex method and a splitting variable approach that is suitable for the Interior Point Methods. A crash procedure that generates an advanced starting solution for the Simplex method is developed. Computational results are reported with both the representations. Although some of the models presented here are very large (over 25000 constraints and 75000 variables), our computational experience with these problems is quite encouraging.     

Production planning via scenario modelling

Several Linear Programming (LP) and Mixed Integer Programming (MIP) models for the production and capacity planning problems with uncertainty in demand are proposed. In contrast to traditional mathematical programming approaches, we use scenarios to characterize the uncertainty in demand. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield a nonanticipative or implementable policy. Such an approach makes it possible to model nonstationarity in demand as well as a variety of recourse decision types. Two scenario-based models for formalizing implementable policies are presented. The first model is a LP model for multi-product, multi-period, single-level production planning to determine the production volume and product inventory for each period, such that the expected cost of holding inventory and lost demand is minimized. The second model is a MIP model for multi-product, multi-period, single-level production planning to help in sourcing decisions for raw materials supply. Although these formulations lead to very large scale mathematical programming problems, our computational experience with LP models for real-life instances is very encouraging.     

CORO,a modeling and an algorithmic framework for oil supply,transformation and distribution optimization under uncertainty

We present a modeling framework for the optimization of a multiperiod Supply, Transformation and Distribution (STD) scheduling problem under uncertainty on the product demand, spot supply cost and spot selling price. The Hydrocarbon and Chemical sector has been chosen as the pilot area, but the approach has a far more reaching application. A deterministic treatment of the problem provides unsatisfactory results. We use a 2-stage scenario analysis based on a partial recourse approach, where the STD policy can be implemented for a given set of initial time periods, such that the solution for the other periods does not need to be anticipated and, then, it depends on the scenario to occur. In any case, it takes into consideration all the given scenarios. Novel schemes are presented for modeling multiperiod linking constraints, such that they are satisfied through the scenario tree; they are modeled by using a splitting variable scheme, via a reduntant circular linking representation.     

Schumann,a modeling framework for supply chain management under uncertainty

We present a modeling framework for the optimization of a manufacturing, assembly and distribution (MAD) supply chain planning problem under uncertainty in product demand and component supplying cost and delivery time, mainly. The automotive sector has been chosen as the pilot area for this type of multiperiod multiproduct multilevel problem, but the approach has a far more reaching application. A deterministic treatment of the problem provides unsatisfactory results. We use a 2-stage scenario analysis based on a partial recourse approach, where MAD supply chain policy can be implemented for a given set of initial time periods, such that the solution for the other periods does not need to be anticipated and, then, it depends on the scenario to occur. In any case, it takes into consideration all the given scenarios. Very useful schemes are used for modeling balance equations and multiperiod linking constraints. A dual approach splitting variable scheme is been used for dealing with the implementable time periods related variables, via a redundant circular linking representation.     

On the average performance of the adjustable RO and its use as an offline tool for multi-period production planning under uncertainty

Robust optimization (RO) is a distribution-free worst-case solution methodology designed for uncertain maximization problems via a max-min approach considering a bounded uncertainty set. It yields a feasible solution over this set with a guaranteed worst-case value. As opposed to a previous conception that RO is conservative based on optimal value analysis, we argue that in practice the uncertain parameters rarely take simultaneously the values of the worst-case scenario, and thus introduce a new performance measure based on simulated average values. To this end, we apply the adjustable RO (AARC) to a single new product multi-period production planning problem under an uncertain and bounded demand so as to maximize the total profit. The demand for the product is assumed to follow a typical life-cycle pattern, whose length is typically hard to anticipate. We suggest a novel approach to predict the production plan’s profitable cycle length, already at the outset of the planning horizon. The AARC is an offline method that is employed online and adjusted to past realizations of the demand by a linear decision rule (LDR). We compare it to an alternative offline method, aiming at maximum expected profit, applying the same LDR. Although the AARC maximizes the profit against a worst-case demand scenario, our empirical results show that the average performance of both methods is very similar. Further, AARC consistently guarantees a worst profit over the entire uncertainty set, and its model’s size is considerably smaller and thus exhibit superior performance.     

Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution

In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.     

Multicut Benders decomposition algorithm for process supply chain planning under uncertainty

In this paper, we present a multicut version of the Benders decomposition method for solving two-stage stochastic linear programming problems, including stochastic mixed-integer programs with only continuous recourse (two-stage) variables. The main idea is to add one cut per realization of uncertainty to the master problem in each iteration, that is, as many Benders cuts as the number of scenarios added to the master problem in each iteration. Two examples are presented to illustrate the application of the proposed algorithm. One involves production-transportation planning under demand uncertainty, and the other one involves multiperiod planning of global, multiproduct chemical supply chains under demand and freight rate uncertainty. Computational studies show that while both the standard and the multicut versions of the Benders decomposition method can solve large-scale stochastic programming problems with reasonable computational effort, significant savings in CPU time can be achieved by using the proposed multicut algorithm.     

On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse management

A new scheme for dealing with uncertainty in scenario trees is presented for dynamic mixed 0–1 optimization problems with strategic and operational stochastic parameters. Let us generically name this type of problems as capacity expansion planning (CEP) in a given system, e.g., supply chain, production, rapid transit network, energy generation and transmission network, etc. The strategic scenario tree is usually a multistage one, and the replicas of the strategic nodes root structures in the form of either a special scenario graph or a two-stage scenario tree, depending on the type of operational activity in the system. Those operational scenario structures impact in the constraints of the model and, thus, in the decomposition methodology for solving usually large-scale problems. This work presents the modeling framework for some of the risk neutral and risk averse measures to consider for CEP problem solving. Two types of risk averse measures are considered. The first one is a time-inconsistent mixture of the chance-constrained and second-order stochastic dominance (SSD) functionals of the value of a given set of functions up to the strategic nodes in selected stages along the time horizon, The second type is a strategic node-based time-consistent SSD functional for the set of operational scenarios in the strategic nodes at selected stages. A specialization of the nested stochastic decomposition methodology for that problem solving is outlined. Its advantages and drawbacks as well as the framework for some schemes to, at least, partially avoid those drawbacks are also presented.     

Flexible-attribute problems

Problems with significant input-data uncertainty are very common in practical situations. One approach to dealing with this uncertainty is called scenario planning, where the data uncertainty is represented with scenarios. A scenario represents a potential realization of the important parameters of the problem.     

Dynamic dairy facility location and supply chain planning under traffic congestion and demand uncertainty: A case study of Tehran

In this paper, dynamic dairy facility location and supply chain planning are studied through minimizing the costs of facility location, traffic congestion and transportation of raw/processed milk and dairy products under demand uncertainty. The proposed model dynamically incorporates possible changes in transportation network, facility investment costs, monetary value of time and changes in production process. In addition, the time variation and the demand uncertainty for dairy products in each period of the planning horizon is taken into account to determine the optimal facility location and the optimal production volumes. Computational results are presented for the model on a number of test problems. Also, an empirical case study is conducted in order to investigate the dynamic effects of traffic congestion and demand uncertainty on facility location design and total system costs.     

A stochastic aggregate production planning model in a green supply chain: Considering flexible lead times,nonlinear purchase and shortage cost functions

In this paper we develop a stochastic programming approach to solve a multi-period multi-product multi-site aggregate production planning problem in a green supply chain for a medium-term planning horizon under the assumption of demand uncertainty. The proposed model has the following features: (i) the majority of supply chain cost parameters are considered; (ii) quantity discounts to encourage the producer to order more from the suppliers in one period, instead of splitting the order into periodical small quantities, are considered; (iii) the interrelationship between lead time and transportation cost is considered, as well as that between lead time and greenhouse gas emission level; (iv) demand uncertainty is assumed to follow a pre-specified distribution function; (v) shortages are penalized by a general multiple breakpoint function, to persuade producers to reduce backorders as much as possible; (vi) some indicators of a green supply chain, such as greenhouse gas emissions and waste management are also incorporated into the model. The proposed model is first a nonlinear mixed integer programming which is converted into a linear one by applying some theoretical and numerical techniques. Due to the convexity of the model, the local solution obtained from linear programming solvers is also the global solution. Finally, a numerical example is presented to demonstrate the validity of the proposed model.     

Cost/risk balanced management of scarce resources using stochastic programming

We consider the situation when a scarce renewable resource should be periodically distributed between different users by a Resource Management Authority (RMA). The replenishment of this resource as well as users demand is subject to considerable uncertainty. We develop cost optimization and risk management models that can assist the RMA in its decision about striking the balance between the level of target delivery to the users and the level of risk that this delivery will not be met. These models are based on utilization and further development of the general methodology of stochastic programming for scenario optimization, taking into account appropriate risk management approaches. By a scenario optimization model we obtain a target barycentric value with respect to selected decision variables. A successive reoptimization of deterministic model for the worst case scenarios allows the reduction of the risk of negative consequences derived from unmet resources demand. Our reference case study is the distribution of scarce water resources. We show results of some numerical experiments in real physical systems.     

Agricultural planning of annual plants under demand,maturation, harvest,and yield risk

In this study we present a planning methodology for a firm whose objective is to match the random supply of annual premium fruits and vegetables from a number of contracted farms and the random demand from the retailers during the planning period. The supply uncertainty is due to the uncertainty of the maturation time, harvest time, and yield. The demand uncertainty is the uncertainty of weekly demand from the retailers. We provide a planning methodology to determine the farm areas and the seeding times for annual plants that survive for only one growing season in such a way that the expected total profit is maximized. Both the single period and the multi period cases are analyzed depending on the type of the plant. The performance of the solution methodology is evaluated by using numerical experiments. These experiments show that the proposed methodology matches random supply and random demand in a very effective way and improves the expected profit substantially compared to the planning approaches where the uncertainties are not taken into consideration.     

Models for planning capacity expansion of convenience stores under uncertain demand and the value of information

Several stochastic optimization models for planning capacity expansion for convenience store chains (or other similar businesses) are developed that incorporate uncertainty in future demand. All of these models generate schedules for capacity expansion, specifying the size, location, and timing of these expansions in order to maximize the expected profit to the company and to remain within a budget constraint on available resources. The models differ in how uncertainty is incorporated, specifically they differ in the point in the decision-making process that the uncertainty in the demand is resolved. Several measures of the value of information are defined by comparing the results from the different models. Two sample problems are given and their solutions for the various approaches compared.     

Multi-period price promotions in a single-supplier, multi-retailer supply chain under asymmetric demand information

This paper considers a two-stage supply chain in which a supplier serves a set of stores in a retail chain. We consider a two-stage Stackelberg game in which the supplier must set price discounts for each period of a finite planning horizon under uncertainty in retail-store demand. As a mechanism to stimulate sales, the supplier offers periodic off-invoice price discounts to the retail chain. Based on the price discounts offered by the supplier, and after store demand uncertainty is resolved, the retail chain determines individual store order quantities in each period. Because the supplier offers store-specific prices, the retailer may ship inventory between stores, a practice known as diverting. We demonstrate that, despite the resulting bullwhip effect and associated costs, a carefully designed price promotion scheme can improve the supplier’s profit when compared to the case of everyday low pricing (EDLP). We model this problem as a stochastic bilevel optimization problem with a bilinear objective at each level and with linear constraints. We provide an exact solution method based on a Reformulation-Linearization Technique (RLT). In addition, we compare our solution approach with a widely used heuristic and another exact solution method developed by Al-Khayyal (Eur. J. Oper. Res. 60(3):306–314, 1992) in order to benchmark its quality.     

A scenario decomposition approach for stochastic production planning in sawmills

This study considers a real world stochastic multi-period, multi-product production planning problem. Motivated by the challenges encountered in sawmill production planning, the proposed model takes into account two important aspects: (i) randomness in yield and in demand; and (ii) set-up constraints. Rather than considering a single source of randomness, or ignoring set-up constraints as is typically the case in the literature, we retain all these characteristics while addressing real life-size instances of the problem. Uncertainties are modelled by a scenario tree in a multi-stage environment. In the case study, the resulting large-scale multi-stage stochastic mixed-integer model cannot be solved by using the mixed-integer solver of a commercial optimization package, such as CPLEX. Moreover, as the production planning model under discussion is a mixed-integer programming model lacking any special structure, the development of decomposition and cutting plane algorithms to obtain good solutions in a reasonable time-frame is not straightforward. We develop a scenario decomposition approach based on the progressive hedging algorithm, which iteratively solves the scenarios separately. CPLEX is then used for solving the sub-problems generated for each scenario. The proposed approach attempts to gradually steer the solutions of the sub-problems towards an implementable solution by adding some penalty terms in the objective function used when solving each scenario. Computational experiments for a real-world large-scale sawmill production planning model show the effectiveness of the proposed solution approach in finding good approximate solutions.     

Integrated production and distribution scheduling with lifespan constraints

We consider an integrated production and distribution scheduling problem in a make-to-order business scenario. A product with a short lifespan (e.g., perishable or seasonal) is produced at a single production facility with a limited production rate. This means that the product expires in a constant time after its production is finished. Orders are received from a set of geographically dispersed customers, where a demand for the product and a time window for the delivery is associated with each customer for the planning period. A single vehicle with non-negligible traveling times between the locations is responsible for the deliveries. Due to the limited production and distribution resources, possibly not all customers may be supplied within their time windows or the lifespan. The problem consists in finding a selection of customers to be supplied such that the total satisfied demand is maximized. We extend the work by Armstrong et al. (Annals of Operations Research 159(1):395–414, 2008) on the problem for fixed delivery sequences by pointing out an error in their branch and bound algorithm and presenting a corrected variant. Furthermore, we introduce model extensions for handling delays of the production start as well as for variable production and distribution sequences. Efficient heuristic solution algorithms and computational results for randomly generated instances are presented.     

Network planning under uncertainty with an application to hydropower generation

Summary We present a general modeling framework for therobust optimization of linear network problems with uncertainty in the values of the right-hand side. In contrast to traditional approaches in mathematical programming, we use scenarios to characterize the uncertainty. Solutions are obtained for each scenario and these individual scenarios are aggregated to yield a nonanticipative or implementable policy that minimizes the regret of wrong decisions. A given solution is termed robust if it minimizes the sum over the scenarios of the weighted upper difference between the objective function value for the solution and the objective function value for the optimal solution for each scenario, while satisfying certain nonanticipativity constraints. This approach results in a huge model with a network submodel per scenario plus coupling constraints. Several decomposition approaches are considered, namely Dantzig-Wolfe decomposition, various types of Benders decomposition and different quadratic network approaches for approximating Augmented Lagrangian decomposition. We present computational results for these methods, including two implementation versions of the Lagrangian based method: a sequential implementation and a parallel implementation on a network of three workstations.     

A heuristic methodology for sizing a large-scale system of constrained, reusable resources

This paper proposes a methodology for sizing certain large-scale systems of reusable, capacity-constrained resources engaged in tasks of varying duration. A heuristic program schedules resources throughout a finite planning horizon using two decision variables: varying resource capacity for meeting demand and varying task duration. A model of the problem and heuristic scheduling program are presented. A sequential, iterative sizing procedure determines the number of system resources to meet demand at each stage of the problem. Results compare the methodology with heuristics used in practice to schedule resources and size a real-world, large-scale training system.     

Stochastic multi-site capacity planning of TFT-LCD manufacturing using expected shadow-price based decomposition

This paper presents a stochastic optimization model and efficient decomposition algorithm for multi-site capacity planning under the uncertainty of the TFT-LCD industry. The objective of the stochastic capacity planning is to determine a robust capacity allocation and expansion policy hedged against demand uncertainties because the demand forecasts faced by TFT-LCD manufacturers are usually inaccurate and vary rapidly over time. A two-stage scenario-based stochastic mixed integer programming model that extends the deterministic multi-site capacity planning model proposed by Chen et al. (2010) [1] is developed to discuss the multi-site capacity planning problem in the face of uncertain demands. In addition a three-step methodology is proposed to generate discrete demand scenarios within the stochastic optimization model by approximating the stochastic continuous demand process fitted from the historical data. An expected shadow-price based decomposition, a novel algorithm for the stage decomposition approach, is developed to obtain a near-optimal solution efficiently through iterative procedures and parallel computing. Preliminary computational study shows that the proposed decomposition algorithm successfully addresses the large-scale stochastic capacity planning model in terms of solution quality and computation time. The proposed algorithm also outperforms the plain use of the CPLEX MIP solver as the problem size becomes larger and the number of demand scenarios increases.