A multi-stage stochastic programming approach for production planning with uncertainty in the quality of raw materials and demand

Motivated by the challenges encountered in sawmill production planning, we study a multi-product, multi-period production planning problem with uncertainty in the quality of raw materials and consequently in processes yields, as well as uncertainty in products demands. As the demand and yield own different uncertain natures, they are modelled separately and then integrated. Demand uncertainty is considered as a dynamic stochastic data process during the planning horizon, which is modelled as a scenario tree. Each stage in the demand scenario tree corresponds to a cluster of time periods, for which the demand has a stationary behaviour. The uncertain yield is modelled as scenarios with stationary probability distributions during the planning horizon. Yield scenarios are then integrated in each node of the demand scenario tree, constituting a hybrid scenario tree. Based on the hybrid scenario tree for the uncertain yield and demand, a multi-stage stochastic programming (MSP) model is proposed which is full recourse for demand scenarios and simple recourse for yield scenarios. We conduct a case study with respect to a realistic scale sawmill. Numerical results indicate that the solution to the multi-stage stochastic model is far superior to the optimal solution to the mean-value deterministic and the two-stage stochastic models.     

Replenishment planning in discrete-time, capacitated, non-stationary, stochastic inventory systems

In this paper, we examine a single-product, discrete-time, non-stationary, inventory replenishment problem with both supply and demand uncertainty, capacity limits on replenishment quantities, and service level requirements. A scenario-based stochastic program for the static, finite-horizon problem is presented to determine replenishment orders over the horizon. We propose a heuristic that is based on the first two moments of the random variables and a normal approximation, whose solution is compared with the optimal from a simulation-based optimization method. Computational experiments show that the heuristic performs very well (within 0.25% of optimal, on average) even when the uncertainty is non-normal or when there are periods without any supply. We also present insights obtained from sensitivity analyses on the effects of supply parameters, shortage penalty costs, capacity limits, and demand variance. A rolling-horizon implementation is illustrated.     

Dynamic capacitated lot sizing with random demand and dynamic safety stocks

We present a stochastic version of the single-level, multi-product dynamic lot-sizing problem subject to a capacity constraint. A production schedule has to be determined for random demand so that expected costs are minimized and a constraint based on a new backlog-oriented δ-service-level measure is met. This leads to a non-linear model that is approximated by two different linear models. In the first approximation, a scenario approach based on the random samples is used. In the second approximation model, the expected values of physical inventory and backlog as functions of the cumulated production are approximated by piecewise linear functions. Both models can be solved to determine efficient, robust and stable production schedules in the presence of uncertain and dynamic demand. They lead to dynamic safety stocks that are endogenously coordinated with the production quantities. A numerical analysis based on a set of (artificial) problem instances is used to evaluate the relative performance of the two different approximation approaches. We furthermore show under which conditions precise demand forecasts are particularly useful from a production–scheduling perspective.     

Effect of limited capacity on optimal planning parameters for a multi-item production system with setup times and advance demand information

An analytical production/inventory model to optimise the planning parameters lot-size, safety stock and planned lead time is developed for a stochastic single-stage production system with multiple items and limited capacity. Based on queuing analysis, the influence of item specific lot-sizes on the production lead time distribution is modelled. Applying stochastic advance demand information, the expected values for finished-goods-inventory, backorders and service level are explicitly stated. Numerical optimisation is applied to solve the respective cost minimisation problem and a solution heuristic is developed to support this approach. A numerical study provides managerial insights concerning capacity limitation effects on the optimal planning parameters. Higher shop loads, i.e. tighter capacity constraints, are found to significantly increase optimal lot-size and optimal safety stock. Safety stock and planned lead time are substitutes, an increase of both leads to higher FGI and lower backorders, however, the specific trade-off depends on the demand information quality. A sensitivity analysis investigating other (non-) financial system parameters is conducted as well. The main contribution of this paper is that the interaction of different planning parameters, i.e. lot-size, safety stock and planned lead time, for different items is simultaneously studied for a capacity constrained production/inventory system.     

Lagrangian relaxation method for price-based unit commitment problem

The unit commitment problem consists of determining the schedules for power generating units and the generating level of each unit. The decisions concern which units to commit during each time period and at what level to generate power to meet the electricity demand. The problem is a typical scheduling problem in an electric power system. The electric power industry is undergoing restructuring and deregulation. This article developes a stochastic programming model which incorporates power trading. The uncertainty of electric power demand or electricity price are incorporated into the unit commitment problem. It is assumed that demand and price uncertainty can be represented by a scenario tree. A stochastic integer programming model is proposed in which the objective is to maximize expected profits. In this model, on/off decisions for each generator are made in the first stage. The approach to solving the problem is based on Lagrangian relaxation and dynamic programming.     

Dynamic planned safety stocks in supply networks

Safety stocks are commonly used in inventory management for tactically planning against uncertainty in demand and/or supply. The usual approach is to plan a single safety stock value for the entire planning horizon. More advanced methods allow for dynamically updating this value. We introduce a new line of research in inventory management: the notion of planning time-phased safety stocks. We assert that planning a time-phased set of safety stocks over a planning horizon makes sense because larger safety stocks are appropriate in times of greater uncertainty while lower safety stocks are more appropriate when demand and/or supply are more predictable. Projecting a vector of safety stock values is necessary to assure upstream members in the supply network have advanced warning of changes. We perform an empirical study of U.S. industry, which demonstrates that significant savings can be achieved by employing dynamic planned safety stocks, confirming recent case study reports. We provide a simple optimisation model for the problem of minimising inventory given a vector of safety stock targets. We propose a computationally efficient solution procedure and demonstrate its implementation in an MRP/ERP system. We then illustrate an MRP/ERP planning system feature, which employs a dynamic planned safety stock module that supports a production planner by showing the inventory implications of safety stock plans.     

Strategic configuration of flexible electronics assembly facilities facing stochastic requirements

Flexible configuration of manufacturing facilities is a key strategy for efficiently improving market responsiveness and market share in the face of uncertain future product demand. Flexible facility configurations can produce an efficient production system that allows higher capacity utilization given uncertainty in product demand and mix. The aim of this paper is to consider the alternative choices of flexible equipment available at the strategic planning level and to make decisions about the facility design and configuration that best suits the specific needs of the manufacturing system under consideration. A chance constrained mixed integer programming model for strategic configuration and capacity planning of flexible multiple-stage production facilities under time-varying production requirements is introduced in this paper. It is an integrated model that determines the number of assembly lines required, the flexible automation levels required in each line, capacity levels, and product assignments/reassignments for a multiple-stage production system, considering the stochastic nature of the demand. A two-step heuristic based on genetic algorithms is proposed and tested. Experimental results indicate that the two-step heuristic performs well in terms of both computation speed and solution accuracy.     

Dynamic determination of vessel speed and selection of bunkering ports for liner shipping under stochastic environment

In this work, we study a liner shipping operational problem which considers how to dynamically determine the vessel speed and refueling decisions, for a single vessel in one service route. Our model is a multi-stage dynamic model, where the stochastic nature of the bunker prices is represented by a scenario tree structure. Also, we explicitly incorporate the uncertainty of bunker consumption rates into our model. As the model is a large-scale mixed integer programming model, we adopt a modified rolling horizon method to tackle the problem. Numerical results show that our framework provides a lower overall cost and more reliable schedule compared with the stationary model of a related work.     

Supply chain capacity and outsourcing decisions: the dynamic interplay of demand and supply uncertainty

We study the interplay of demand and supply uncertainty in capacity and outsourcing decisions in multi-stage supply chains. We consider a firm's investment in two stages of a supply chain (Stage 1 models the “core” activities of the firm, while Stage 2 are the “non-core” activities). The firm invests in these two stages in order to maximize the multi-period, discounted profit. We consider how non-stationary stochastic demand affects the outsourcing decisions. We also consider how investment levels are affected by non-stationary stochastic supply when the market responds to the firm's investments. We characterize the optimal capacity investment decisions Tor the single- and multi-period versions of our model and focus on how changes in supply and demand uncertainly affect the extent of outsourcing. We find that as the responsiveness of the market to investments made by the firm increases, the reliance on outsourcing generally increases. While greater supply and greater demand have the expected effect on investments, decreases in variability are not as straightforward. Greater supply uncertainty increases the need for vertical integration while greater demand uncertainty increases the reliance on outsourcing. In the multi-period model, we find that the nature of adjustments in capacity based on changes in demand or supply follows from the comparative statics of the single-period model, although whether outsourcing increases or decreases depends on the costs of adjusting capacity.     

A mathematical model for vehicle routing problem under endogenous uncertainty

In this study, a multistage stochastic programming (SP) model is presented for a variant of single-vehicle routing problem with stochastic demands from a dynamic viewpoint. It is assumed that the actual demand of a customer becomes known only when the customer is visited. This problem falls into the category of SP with endogenous uncertainty and hence, the scenario tree is decision-dependent. Therefore, nonanticipativity of decisions is ensured by conditional constraints making up a large portion of total constraints. Thus, a novel approach is proposed that considerably reduces the problem size without any effect on the solution space. Computational results on some test problems are reported.     

Capacitated disassembly scheduling with random demand

This paper considers disassembly scheduling, which is the problem of determining the quantity and timing of the end-of-use/life products to be disassembled while satisfying the demand for their parts obtained from disassembling the products over a planning horizon. This paper focuses on the problem with stochastic demand of parts/modules, capacity restrictions on disassembly resources, and multiple product types with a two-level product structure. The two-level product structure implies that an end-of-use/life product is hierarchically decomposed into two levels where the first level corresponds to the parts/modules and the second level corresponds to the product. We formulate the problem as a stochastic inventory model and to solve the problem we propose a Lagrangian heuristic algorithm as well as an optimisation algorithm for the sub-problems obtained from Lagrangian decomposition. The test results on randomly generated problems show that the Lagrangian heuristic algorithm demonstrates good performance in terms of solution quality and time.     

Semiconductor capacity planning: stochastic modelingand computational studies

This paper presents a multistage stochastic programming model for strategic capacity planning at a major US semiconductor manufacturer. Main sources of uncertainty in this multi-year planning problem include demand of different technologies and capacity estimations for each fabrication (fab) facility. We test the model using real-world scenarios requiring the determination of capacity planning for 29 technology categories among five fab facilities. The objective of the model is to minimize the gaps between product demands and the capacity allocated to the technology specified by each product. We consider two different scenario-analysis constructs: first, an independent scenario structure where we assume no prior information and the model systematically enumerates possible states in each period. The states from one period to another are independent from each other. Second, we consider an arbitrary scenario construct, which allows the planner to sample/evaluate arbitrary multi-period scenarios that captures the dependency between periods. In both cases, a scenario is defined as a multi-period path from the root to a leaf in the scenario tree. We conduct intensive computational experiments on these models using real data supplied by the semiconductor manufacturer. The purpose of our experiments is two-fold: first to examine different degree of scenario aggregation and its effects on the independent model to achieve high-quality solution. Using this as a benchmark, we then compare the results from the arbitrary model and illustrate the different uses of the two scenario constructs. We show that the independent model allows a varying degree of scenario aggregation without significant prior information, while the arbitrary model allows planners to play out specific scenarios given prior information.     

Optimal positioning of safety stocks in MRP

The positioning of safety stock in multi-echelon production networks operating in an MRP environment is considered. Our aim is to maximize the service level achieved for a given total amount of safety stock. Most previous research considering MRP environments has been empirical or heuristic, but the approach we take is analytic and concentrates on two network types: serial and divergent networks. Using previous results on the MRP ordering logic, we show that in serial networks the optimal policy positions all safety stock at the end stock-point. This result is independent of the stochastic nature of the demand, the type of uncertainty and the measure of service used. The analysis of divergent networks is more complicated because of the need for material rationing. We show that the optimal policy may depend on the total amount of safety stock available, the variability of the demand, the structure of the lead times, the choice of the rationing policy and the measure of service used.     

Joint optimization of lot-sizes,safety stocks and safety lead times in an MRP system

This paper reports on a simulation study of an MRP system affected by stochastic demand and stochastic lead times. Experiments are conducted to assess the impact of three data sets: the amount of lead time variability, the amount of demand variability, and the influence of the stockout cost/inventory holding cost ratio. Lot-sizes, safety stocks and lead times are optimized using simulated annealing. The effects of either using safety stocks or safety lead times are compared to each other with the purpose of finding the best method for protection against uncertainties in lead time and demand.     

Scenario-based approach for flexible resource loading under uncertainty

Order acceptance decisions in manufacture-to-order environments are often made based on incomplete or uncertain information. To quote reliable due dates in order processing, manage resource capacity adequately and take into account uncertainty, the paper presents and analyses models and tools for more robust resource loading. We refer to the problem as flexible resource loading under uncertainty. We propose a scenario-based solution approach that can deal with a wide range of uncertainty types. The approach is based on an MILP to find a plan with minimum expected costs over all relevant scenarios. To solve this MILP, we propose an exact branch-and-price algorithm. Further, we propose a much faster improvement heuristic based on an LP (linear programming) approximation. A disadvantage of the scenario-based MILP, is that a large number of scenarios may make the model intractable. We therefore propose an approximate approach that uses the aforementioned solution techniques and only a sample of all scenarios. Computational experiments show that, especially for instances with sufficient slack, solutions obtained with deterministic techniques that only use the expected scenario can be significantly improved with respect to their expected costs (i.e. robustness). We also show that for large instances, our heuristics outperform the exact approach given a maximum computation time as a stopping criterion. Moreover, it turns out that using a small sample of selected scenarios generally yields better results than using all scenarios.     

Setting safety stocks in multi-stage inventory systems under rolling horizon mathematical programming models

This paper considers the problem of determining safety stocks in multi-item multi-stage inventory systems that face demand uncertainties. Safety stocks are necessary to make the supply chain, which is driven by forecasts of customer orders, responsive to (demand) uncertainties and to achieve predefined target service levels. Although there exists a large body of literature on determining safety stock levels, this literature does not provide an effective methodology that can address complex multi-constrained supply chains. In this paper, the problem of determining safety stocks is addressed by a simulation based approach, where the simulation studies are based on solving the supply chain planning problem (formulated as a mathematical programming model) in a rolling horizon setting. To demonstrate the utility of the proposed approach, an application of the approach at Organon, a worldwide operating biopharmaceutical company, will be discussed.     

Remanufacturing lotsizing with stochastic lead-time resulting from stochastic quality of returns

In the current paper, we model the duration of recovery of used products as a variable that depends on each unit’s quality. Because of the uncertainty related to returned units’ quality, the necessary time for the recovery of a lot is a random variable. We provide analytical expressions for the optimisation of recovery planning decisions under different assumptions regarding quality and demand characteristics. In addition, through an extensive numerical study, we examine the impact of the different parameters on the necessity to consider explicitly the stochastic nature of recovery lead-time. Moreover, we discuss the advisability of establishing procedures for the classification of returns according to their quality condition. As our findings indicate, overlooking quality uncertainty can increase related costs considerably because of poor process coordination. Furthermore, ignoring variability may result in undue overestimation of the efficiency of lot-sizing policies. On the other hand, the establishment of quality assessment procedures is worthwhile only when the stochastic behaviour of quality cannot be taken into account explicitly.     

Two-stage stochastic master production scheduling under demand uncertainty in a rolling planning environment

This paper proposes a scenario-based two-stage stochastic programming model with recourse for master production scheduling under demand uncertainty. We integrate the model into a hierarchical production planning and control system that is common in industrial practice. To reduce the problem of the disaggregation of the master production schedule, we use a relatively low aggregation level (compared to other work on stochastic programming for production planning). Consequently, we must consider many more scenarios to model demand uncertainty. Additionally, we modify standard modelling approaches for stochastic programming because they lead to the occurrence of many infeasible problems due to rolling planning horizons and interdependencies between master production scheduling and successive planning levels. To evaluate the performance of the proposed models, we generate a customer order arrival process, execute production planning in a rolling horizon environment and simulate the realisation of the planning results. In our experiments, the tardiness of customer orders can be nearly eliminated by the use of the proposed stochastic programming model at the cost of increasing inventory levels and using additional capacity.     

需求不确定的网络瓶颈容量扩张决策模型

使用一组情景来描述需求的不确定性,要求在所有情景下最大的网络扩张成本最小.建立了情景规划模型,提出分解算法,首先求出每种情景下需要扩张的边及其扩张的容量,然后对所有需要扩张的边取其并集,需要扩张的边的容量取其最大,最后求出最小的扩张成本.计算结果表明分解算法能够大大提高求解速度.     

A Heuristic for Multiple Lot Sizing For an Order Under Variable Yield

Consider a job shop which must completely fill a large make-to-order demand of a product where production yield is highly variable. After a production lot is completed, if the total output of satisfactory units is inadequate to satisfy the demand, then a new run (with associated setup cost) is made. When the output of good units exceeds the demand, then the excess units are scrapped (with possible salvage value). The optimal lot size minimizes the total of production, setup, holding, shortage, and scrap costs. A heuristic is developed based on the incremental cost of increasing the lot size by one unit. The computational ease and excellent cost performance of the heuristic favor its use in place of the mathematically optimal solution obtained by dynamic programming. Real world manufacturing applications and additional properties of the model are also discussed.