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.     

Production planning with uncertainty in the quality of raw materials: a case in sawmills

Motivated by sawmill production planning, this paper investigates multi-period, multi-product (MPMP) production planning in a manufacturing environment with non-homogeneous raw materials, and consequently random process yields. A two-stage stochastic program with recourse is proposed to address the problem. The random yields are modelled as scenarios with stationary probability distributions during the planning horizon. The solution methodology is based on the sample average approximation (SAA) scheme. The stochastic sawmill production planning model is validated through the Monte Carlo simulation. The computational results for a real medium capacity sawmill highlight the significance of using the stochastic model as a viable tool for production planning instead of the mean-value deterministic model, which is a traditional production planning tool in many sawmills.     

A Lagrangean relaxation based approach for the capacity allocation problem in flexible manufacturing systems

This study considers the operation assignment and capacity allocation problem in flexible manufacturing systems. A set of operations is selected to be processed and assigned to the machines together with their required tools. The purchase or usage of the required tools incurs a cost. The machines have scarce time and tool magazine capacities. The objective is to maximize the total weight of the assigned operations minus the total tooling costs. We use Lagrangean relaxation approach to obtain upper and lower bounds on the optimal objective function values. The computational experiments show that our approach provides near optimal bounds in reasonable solution times.     

Heuristics for determining economic processing rates in a flexible manufacturing system

In this paper, models are presented for determining economic processing speeds and tool loading to minimize the makespan required to produce a given set of parts in a flexible manufacturing system. Using Taylor's tool life equation, models for determining the optimal processing speeds and the tools to be loaded into finite capacity machine magazines are formulated to minimize the maximum processing time in the system. These problems are evaluated for computational complexity, and several heuristics for obtaining good feasible solutions to the problem are discussed. The quality of the solutions obtained using these heuristics is evaluated by computational experiments against lower bounds established by either relaxations or optimal solutions when possible.     

Tool capacity planning for semiconductor fabrication facilities under demand uncertainty

This research is motivated by issues faced by a large manufacturer of semiconductor devices. Semiconductor manufacturing companies allocate millions of dollars every year for new types of machine tools for their facilities. Typically these are special purpose machine tools which are made to order. The rate of change in products and technology makes it difficult for manufacturers to have a good estimate of future tool requirements. Further, manufacturers experience a long lead time while procuring these tools. In this paper, we model the tool capacity planning problem under uncertainty in demand. The number of tools required in a facility is sufficiently large (nearly hundred or more tools) to make it nearly impossible to obtain efficient exact algorithms. We provide heuristics to find efficient tool procurement plans and test their quality using lower bounds on the formulation.     

A dynamic programming approach for the airport capacity allocation problem

In most of the optimization models developed to manage airportsoperations, arrivals and departures capacities are treated asindependent variables: that is the number of flights allowedto take off does not affect the number of landings in any unitof time, and vice versa. This assumption is seldom verifiedin most of the congested airports, where many interactions betweenarrivals and departures take place. In this paper, we face the problem of finding the optimal trade-offbetween the number of arrivals and departures in order to reducea delay function of all the flights, using a more realisticrepresentation of the airport capacity, i.e. the capacity envelope. Under the assumption of piecewise linear convex capacity envelopesand of the exact interpolation of all the Pareto-optimal operationalpoints, we show that the problem can be formulated as a linearprogramming model. For general airport capacity envelopes, wepropose a dynamic programming formulation with a correspondingbackward solution algorithm, which is robust, easy to implementand has a linear computational complexity. The algorithm performancesare evaluated on different realistic scenarios, and the optimalsolutions are compared with those computed by a greedy algorithm,which can be seen as an approximation of the current decisionprocedures. The percentage deviation of the cost of these twosolutions ranges from 3.98 to 35.64%.     

An application of Lagrangian relaxation to a capacity planning problem under uncertainty

A supply chain network-planning problem is presented as a two-stage resource allocation model with 0-1 discrete variables. In contrast to the deterministic mathematical programming approach, we use scenarios, to represent the uncertainties in demand. This formulation leads to a very large scale mixed integer-programming problem which is intractable. We apply Lagrangian relaxation and its corresponding decomposition of the initial problem in a novel way, whereby the Lagrangian relaxation is reinterpreted as a column generator and the integer feasible solutions are used to approximate the given problem. This approach addresses two closely related problems of scenario analysis and two-stage stochastic programs. Computational solutions for large data instances of these problems are carried out successfully and their solutions analysed and reported. The model and the solution system have been applied to study supply chain capacity investment and planning.     

Joint effect of stock threshold level and production policy on an unreliable production environment

In this article we develop an economic manufacturing quantity (EMQ) model subject to stochastic machine breakdown, repair and stock threshold level (STL). Instead of constant production rate, in this model production rate is considered as a decision variable. Since, the stress of the machine depends on the production rate, failure rate of the machine will be a function of the production rate. Again, in this article consideration of safety stock in all existing literature is replaced by the concept of stock threshold level (STL). Further, extra capacity of the machine is considered to buffer against the possible uncertainties of the production process where machine capacity is predetermined. The basic model is developed under general failure and general repair time distributions. Since, the assumption of variable production rate makes the objective function quite complex, so main emphasis is given on computational methodology to solve the present problem. We suggest two computational algorithms for the determination of production rate and stock threshold level which minimize the expected cost rate in the steady state. Finally, through numerical examples we illustrate the key insights of our model from managerial point of view.     

Managing variances in manufacturing system design

The goal of this paper is to investigate how uncertainties in demand and production should be incorporated into manufacturing system design problems. We examine two problems in manufacturing system design: the resource allocation problem and the product grouping problem. In the resource allocation problem, we consider the issue of how to cope with uncertainties when we utilize two types of resources: actual processing capacity and stored capacity (inventory). A closed form solution of the optimal allocation scheme for each type of capacity is developed, and its performance is compared to that of the conventional scheme where capacity allocation and inventory control decisions are made sequentially. In the product grouping problem, we consider the issue of how we design production lines when each line is dedicated to a certain set of products. We formulate a mathematical program in which we simultaneously determine the number of production lines and the composition of each line. Two heuristics are developed for the problem.     

A two-level hedging point policy for controlling a manufacturing system with time-delay,demand uncertainty and extra capacity

This paper focuses on the production control of a manufacturing system with time-delay, demand uncertainty and extra capacity. Time-delay is a typical feature of networked manufacturing systems (NMS), because an NMS is composed of many manufacturing systems with transportation channels among them and the transportation of materials needs time. Besides this, for a manufacturing system in an NMS, the uncertainty of the demand from its downstream manufacturing system is considered; and it is assumed that there exist two-levels of demand rates, i.e., the normal one and the higher one, and that the time between the switching of demand rates are exponentially distributed. To avoid the backlog of demands, it is also assumed that extra production capacity can be used when the work-in-process (WIP) cannot buffer the high-level demands rate. For such a manufacturing system with time-delay, demand uncertainty and extra capacity, the mathematical model for its production control problem is established, with the objective of minimizing the mean costs for WIP inventory and occupation of extra production capacity. To solve the problem, a two-level hedging point policy is proposed. By analyzing the probability distribution of system states, optimal values of the two hedging levels are obtained. Finally, numerical experiments are done to verify the effectiveness of the control policy and the optimality of the hedging levels.     

Managing production with flexible capacity deployment for serial multi-stage manufacturing systems

This paper presents a model for serial multi-stage manufacturing systems facing variability from two sources. One source is demand uncertainty; the other is manufacturing uncertainty associated with all manufacturing stages. A production control policy based on the planned lead time and the manufacturing capacity requirement is developed. It is shown that this production control policy has the effect of reducing the variance of production output for all manufacturing stages. Some specific analyses are provided to illustrate the production control policy developed. The model developed provides a vehicle for examining the interrelationships among the production output, the planned lead time and the actual manufacturing flow time. The risk-pooling value over both demand randomness and manufacturing uncertainty, which is achieved through consolidating some manufacturing capacity and deploying flexible capacity among the manufacturing stages, is analyzed. This risk-pooling value can be realized in the form of either reduced manufacturing flow time or increased effective capacity to meet more demand. It is shown that the risk-pooling value increases as the planned lead time decreases.     

Designing multi-echelon service parts networks with finite repair capacity

We propose an approach to model and solve the joint problem of facility location, inventory allocation and capacity investment in a two echelon, single-item, service parts supply chain with stochastic demand. The objective of the decision problem is to minimize the total expected costs associated with (1) opening repair facilities, (2) assigning each field service location to an opened facility, (3) determining capacity levels of the opened repair facilities, and (4) optimizing inventory allocation among the locations. Due to the size of the problem, computational efficiency is essential. The accuracy of the approximations and effectiveness of the approach are analyzed with two numerical studies. The approach provides optimal results in 90% of scenarios tested and was within 2% of optimal when it did not.We explore the impact of capacity utilization, inventory availability, and lead times on the performance of the approach. We show that including tactical considerations jointly with strategic network design resulted in additional cost savings from 3% to 12%. Our contribution is the development of a practical model and approach to support the decision making process of joint facility location and multi-echelon inventory optimization.     

Application of decision analysis techniques to the Weber facility location problem

A location problem with future uncertainties about the data is considered. Several possible scenarios about the future values of the parameters are postulated. However, it is not clear which of these scenarios will actually happen. We find the location that will best accommodate the possible scenarios. Four rules utilized in decision theory are examined: the expected value rule, the optimistic rule, the pessimistic rule, and the minimax regret rule. The solution for the squared Euclidean distance is explicitly found. Algorithms are suggested for general convex distance metrics. An example problem is solved in detail to illustrate the findings, and computational experiments with randomly generated problems are reported.     

Managing inventory and production capacity in start-up firms

We consider the problem of managing inventory and production capacity in a start-up manufacturing firm with the objective of maximising the probability of the firm surviving as well as the more common objective of maximising profit. Using Markov decision process models, we characterise and compare the form of optimal policies under the two objectives. This analysis shows the importance of coordination in the management of inventory and production capacity. The analysis also reveals that a start-up firm seeking to maximise its chance of survival will often choose to keep production capacity significantly below the profit-maximising level for a considerable time. This insight helps us to explain the seemingly cautious policies adopted by a real start-up manufacturing firm.     

Managing capacity flexibility in make-to-order production environments

This paper addresses the problem of managing flexible production capacity in a make-to-order (MTO) manufacturing environment. We present a multi-period capacity management model where we distinguish between process flexibility (the ability to produce multiple products on multiple production lines) and operational flexibility (the ability to dynamically change capacity allocations among different product families over time). For operational flexibility, we consider two polices: a fixed allocation policy where the capacity allocations are fixed throughout the planning horizon and a dynamic allocation policy where the capacity allocations change from period to period. The former approach is modeled as a single-stage stochastic program and solved using a cutting-plane method. The latter approach is modeled as a multi-stage stochastic program and a sampling-based decomposition method is presented to identify a feasible policy and assess the quality of that policy. A computational experiment quantifies the benefits of operational flexibility and demonstrates that it is most beneficial when the demand and capacity are well-balanced and the demand variability is high. Additionally, our results reveal that myopic operating policies may lead a firm to adopt more process flexibility and form denser flexibility configuration chains. That is, process flexibility may be over-valued in the literature since it is assumed that a firm will operate optimally after the process flexibility decision. We also show that the value of process flexibility increases with the number of periods in the planning horizon if an optimal operating policy is employed. This result is reversed if a myopic allocation policy is adopted instead.     

The stochastic U-line balancing problem: A heuristic procedure

Many heuristics have been proposed for the assembly line balancing problem due to its computational complexity and difficulty in identifying an optimal solution. Still, the basic line balancing model fails to consider a number of realistic elements. The implementation of a Just-In-Time manufacturing system generally entails the replacement of traditional straight assembly lines with U-shaped lines. An important issue in the U-line balancing problem is the consideration of task time variability due to human factors or various disruptions. In this paper, we consider the stochastic U-line balancing problem. A hybrid heuristic is presented consisting of an initial feasible solution module and a solution improvement module. To gain insight into its performance, we analyze the heuristic under different scenarios of task time variability. Computational results clearly demonstrate the efficiency and robustness of our algorithm.     

Managing manufacturing risks by using capacity options

In this study, we investigate the strategy of increasing production capacity temporarily through contingent contractual agreements with short-cycle manufacturers to manage the risks associated with demand volatility. We view all these agreements as capacity options. More specifically, we consider a manufacturing company that produces a replenishment product that is sold at a retailer. The demand for the product switches randomly between a high level and a low level. The production system has enough capacity to meet the demand in the long run. However, when the demand is high, it does not have enough capacity to meet the instantaneous demand and thus has to produce to stock in advance. Alternatively, a contractual agreement with a short-cycle manufacturer can be made. This option gives the right to receive additional production capacity when needed. There is a fixed cost to purchase this option for a period of time and, if the option is exercised, there is an additional per unit exercise price which corresponds to the cost of the goods produced at the short-cycle manufacturer. We formulate the problem as a stochastic optimal control problem and analyse it analytically. By comparing the costs between two cases where the contract with the short-cycle manufacturer is used or not, the value of this option is evaluated. Furthermore, the effect of demand variability on this contract is investigated.     

Stochastic binary problems with simple penalties for capacity constraints violations

This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly ${\mathcal{N}\mathcal{P}}$ -hard in general. We provide pseudo-polynomial algorithms for three special cases of the problem: constant weights and capacity uniformly distributed, subset sum with Gaussian weights and strictly positively distributed random capacity, and subset sum with constant weights and arbitrary random capacity. We then turn to a branch-and-cut algorithm based on the outer approximation of the objective function. We provide computational results for the stochastic knapsack problem (i) with Gaussian weights and constant capacity and (ii) with constant weights and capacity uniformly distributed, on randomly generated instances inspired by computational results for the knapsack problem.     

A model for strategic planning under uncertainty

Summary In this paper the multi-period strategic planning problem for a consumer sumer product manufacturing chain is considered. Our discussion is focused on investment decisions which, are economically optimal over the whole planning horizonT, while meeting customer demands and conforming to technological requirements. In strategic planning, time and uncertainty play important roles. The uncertainties in the model are due to different levels of forecast demands, cost estimates and equipment behaviour. The main aim of this paper is to develop and analyse a multiperiod stochastic model representing the entire manufacturing chain, from the acquisitions of raw material to the delivering of final products. The resulting optimization problem is computationally intractable because of the enormous, and sometimes unrealistic, number of scenarios that must be considered in order to identify the optimal planning strategy. We propose two different solution approaches; firstly, we apply a scenario risk analysis giving the related results of experiments on a particular real data set. We then describe and investigate an Integer Stochastic Programming formulation of the problem and propose, as a solution technique, a variation of Benders decomposition method, namely theL-shaped method.     

Iterative algorithms for part grouping and loading in cellular reconfigurable manufacturing systems

A reconfigurable manufacturing system (RMS), one of state-of-the-art manufacturing system technologies, is the one designed at the outset for rapid changes in its hardware and software components in order to quickly adjust its production capacity and functionality in response to market or system changes. In this study, we consider a cellular RMS with multiple reconfigurable machining cells (RMCs), each of which has numerical control machines, a setup station, and an automatic material handling and storage system. Each machine within the RMC has an automatic tool changer and a tool magazine of a limited capacity. Two important operational problems, part grouping and loading, are considered in this study. Part grouping is the problem of allocating parts to RMCs, and loading is the problem of allocating operations and their cutting tools to machines within the RMC. An integer programming model is suggested to represent the two problems at the same time for the objective of balancing the workloads assigned to machines. Then, due to the complexity of the problem, we suggest two iterative algorithms in which the two problems are solved repeatedly until a solution is obtained. Computational experiments were done on various test instances and the results are reported.