Production planning with approved vendor matrices for a hard-disk drive manufacturer

We develop an optimal production schedule for a manufacturer of hard-disk drives that offers its customers the approved vendor matrix (AVM) as a competitive advantage. An AVM allows each customer to pick and choose the various product component vendors for individual or pairs of components constituting their product. The production planning problem faced by the manufacturer is to meet customer demand as precisely as possible while observing the matrix restrictions and also the limited availability of production resources. We formulate this problem as a linear programming model with a large number of variables, and present a solution procedure based on the column generation technique. A special class of the problem is then studied, whereby the number of production setups in each period is limited and discrete. We modify our formulation into a mixed-integer problem, and proceed to develop procedures that can obtain good feasible solutions using linear programming rounding techniques.     

p-Hub approach for the optimal park-and-ride facility location problem

Park and Ride facilities (P&R) are car parks at which users can transfer to public transportation to reach their final destination. We propose a mixed linear programming formulation to determine the location of a fixed number of P&R facilities so that their usage is maximized. The facilities are modeled as hubs. Commuters can use one of the P&R facilities or choose to travel by car to their destinations, and their behavior follows a logit model. We apply a p-hub approach considering that users incur in a known generalized cost of using each P&R facility as input for the logit model. For small instances of the problem, we propose a novel linearization of the logit model, which allows transforming the binary nonlinear programming problem into a mixed linear programming formulation. A modification of the Heuristic Concentration Integer (HCI) procedure is applied to solve larger instances of the problem. Numerical experiments are performed, including a case in Queens, NY. Further research is proposed.     

Workforce planning at USPS mail processing and distribution centers using stochastic optimization

Service organizations that operate outside the normal 8-hour day and face wide fluctuations in demand constantly struggle to optimize the size and composition of their workforce. Recent research has shown that improved personnel scheduling methods that take demand uncertainty into account can lead to significant reductions in labor costs. This paper addresses a staff planning and scheduling problem that arises at United States Postal Service (USPS) mail processing & distribution centers (P&DCs) and develops a two-stage stochastic integer program with recourse for the analysis. In the first stage, before the demand is known, the number of full-time and part-time employees is determined for the permanent workforce. In the second stage, the demand is revealed and workers are assigned to specific shifts during the week. When necessary, overtime and casual labor are used to satisfy demand. This paper consists of two parts: (1) the analysis of the demand distribution in light of historical data, and (2) the development and analysis of the stochastic integer programming model. Using weekly demand for a three-year period, we first investigate the possibility that there exists an end-of-month effect, i.e., the week at the end of month has larger volume than the other weeks. We show that the data fail to indicate that this is the case. In the computational phase of the work, three scenarios are considered: high, medium, and low demand. The stochastic optimization problem that results is a large-scale integer program that embodies the full set of contractual agreements and labor rules governing the design of the workforce at a P&DC. The usefulness of the model is evaluated by solving a series of instances constructed from data provided by the Dallas facility. The results indicate that significant savings are likely when the recourse problem is used to help structure the workforce. This work was supported in part by the National Science Foundation under grants DMI-0218701 and DMI-0217927.     

A multi-period ordering and clearance pricing model considering the competition between new and out-of-season products

The joint management of pricing and inventory for perishable products has become an important problem for retailers. This paper investigates a multi-period ordering and clearance pricing model under consideration of the competition between new and out-of-season products. In each period, the ordering quantity of the new product and the clearance price of the out-of-season product are determined as decision variables before the demand is realized, and the unsold new product becomes the out-of-season one of the next period. We establish a finite-horizon Markov decision process model to formulate this problem and analyze its properties. A traditional dynamic program (DP) approach with two-dimensional search is provided. In addition, a myopic policy is derived in which only the profit of the current period is considered. Finally, we apply genetic algorithm (GA) to this problem and design a GA-based heuristic approach, showing by comparison among different algorithms that the GA-based heuristic approach is more performance sound than the myopic policy and much less time consuming than the DP approach.     

The value of dynamic pricing for cores in remanufacturing with backorders

In remanufacturing, the supply of used products and the demand for remanufactured products are usually mismatched because of the great uncertainties on both sides. In this paper, we propose a dynamic pricing (DP) policy to balance this uncertain supply and demand. Specifically, we study a remanufacturer’s problem of pricing a single class of cores with random price-dependent returns and random demand for the remanufactured products with backlogs. We model this pricing task as a continuous-time Markov decision process, which addresses both the finite and infinite horizon problems, and provide managerial insights by analysing the structural properties of the optimal policy. We then use several computational examples to illustrate the impacts of particular system parameters on pricing policy and the benefit of DP. In addition, the models are extended to account for the price adjustment costs. We show through numerical example that the nice structural properties do not exist any longer, and find when DP is better than static pricing.     

A revenue management approach to address a truck rental problem

This paper describes an application of revenue management techniques and policies in the field of logistics and distribution. In particular, the problem of transportation operators, who offer products for hire, is considered. A product is a truck of a given capacity, which can be rented for one or several time periods, throughout a multi-period planning horizon. The logistic operator can satisfy the demand of a given product with trucks with a capacity greater than that initially required, that is an ‘upgrade’ can take place. In this context, the logistic operator has to decide whether to accept or reject a request and which type of truck should be used to address it. For this purpose, a dynamic programming (DP) formulation of the problem under consideration is devised. The ‘course of dimensionality’ leads to the necessity of introducing different mathematical programming models to represent the problem. The mathematical models we presented are an extension of the well-known approximations for the DP of traditional network capacity management analysis. Based on these models and exploiting revenue management concepts, primal and dual acceptance policies are developed and compared in a computational study.     

A Chance-Constrained Integer Goal Programming Model for Capital Budgeting in the Production Area

The selection of capital projects in a production environment is complicated by the existence of multiple and conflicting goals. Typical production objectives for cost minimization often conflict with goals for quality, environmental standards, labor relations, etc. This problem of project selection is further complicated by the uncertainty inherent in product demand, the key factor in production management. This paper approaches these complications by employing an integer goal programming (to compensate for multiple conflicting objectives) with chance-constrained capabilities (to reflect uncertainty in product demand). The approach is demonstrated via an in-depth case example of a production problem.     

The design of corporate tax structures

We consider the corporate tax structuring problem (TaxSP), a combinatorial optimization problem faced by firms with multinational operations. The problem objective is nonlinear and involves the minimization of the firm's overall tax payments i.e. the maximization of shareholder returns. We give a dynamic programming (DP) formulation of this problem including all existing schemes of tax-relief and income-pooling. We apply state space relaxation and state space descent to the DP recursions and obtain an upper bound to the value of optimal TaxSP solutions. This bound is imbedded in a B&B tree search to provide another exact solution procedure. Computational results from DP and B&B are given for problems up to 22 subsidiaries. For larger size TaxSPs we develop a heuristic referred to as the Bionomic Algorithm (BA). This heuristic is also used to provide an initial lower bound to the B&B algorithm. We test the performance of BA firstly against the exact solutions of TaxSPs solvable by the B&B algorithm and secondly against results obtained for large-size TaxSPs by Simulated Annealing (SA) and Genetic Algorithms (GA). We report results for problems of up to 150 subsidiaries, including some real-world problems for corporations based in the US and the UK. Support for this work was provided by the IST Framework 5 Programme of the European Union, Contract IST2000-29405, Eurosignal ProjectMathematics Subject Classification (2000): 90C39, 91B28     

The optimal control of just-in-time-based production and distribution systems and performance comparisons with optimized pull systems

In just-in-time (JIT) production systems, there is both input stock in the form of parts and output stock in the form of product at each stage. These activities are controlled by production-ordering and withdrawal kanbans. This paper discusses a discrete-time optimal control problem in a multistage JIT-based production and distribution system with stochastic demand and capacity, developed to minimize the expected total cost per unit of time. The problem can be formulated as an undiscounted Markov decision process (UMDP); however, the curse of dimensionality makes it very difficult to find an exact solution. The author proposes a new neuro-dynamic programming (NDP) algorithm, the simulation-based modified policy iteration method (SBMPIM), to solve the optimal control problem. The existing NDP algorithms and SBMPIM are numerically compared with a traditional UMDP algorithm for a single-stage JIT production system. It is shown that all NDP algorithms except the SBMPIM fail to converge to an optimal control.Additionally, a new algorithm for finding the optimal parameters of pull systems is proposed. Numerical comparisons between near-optimal controls computed using the SBMPIM and optimized pull systems are conducted for three-stage JIT-based production and distribution systems. UMDPs with 42 million states are solved using the SBMPIM. The pull systems discussed are the kanban, base stock, CONWIP, hybrid and extended kanban.     

A hybrid method for large-scale short-term scheduling of make-and-pack production processes

Due to the ongoing trend towards increased product variety, fast-moving consumer goods such as food and beverages, pharmaceuticals, and chemicals are typically manufactured through so-called make-and-pack processes. These processes consist of a make stage, a pack stage, and intermediate storage facilities that decouple these two stages. In operations scheduling, complex technological constraints must be considered, e.g., non-identical parallel processing units, sequence-dependent changeovers, batch splitting, no-wait restrictions, material transfer times, minimum storage times, and finite storage capacity. The short-term scheduling problem is to compute a production schedule such that a given demand for products is fulfilled, all technological constraints are met, and the production makespan is minimised. A production schedule typically comprises 500–1500 operations. Due to the problem size and complexity of the technological constraints, the performance of known mixed-integer linear programming (MILP) formulations and heuristic approaches is often insufficient.     

An impulse control problem of a production model with interruptions to follow stochastic demand

The paper deals with the stochastic optimal intervention problem which arises in a production & storage system involving identical items. The requests for items arrive at random and the production of an item can be interrupted during production to meet the corresponding demand. The operational costs considered are due to the stock/backlog, running costs and set up costs associated to interruptions and re-initializations. The process presents distinct behaviour on each of two disjoint identical subsets of the state space, and the state process can only be transferred from one subset to the other by interventions associated to interruptions/re-initializations. A characterization is given in terms of piecewise deterministic Markov process, which explores the aforementioned structure, and a method of solution with assured convergence, that does not require any special initialization, is provided.Additionally, we demonstrate that under conditions on the data, the optimal policy is to produce the item completely in a certain region of the state space of low stock level.     

A scenario‐based stochastic programming model for the control or dummy wafers downgrading problem

The subject of this paper is to study a realistic planning environment in wafer fabrication for the control or dummy (C/D) wafers problem with uncertain demand. The demand of each product is assumed with a geometric Brownian motion and approximated by a finite discrete set of scenarios. A two‐stage stochastic programming model is developed based on scenarios and solved by a deterministic equivalent large linear programming model. The model explicitly considers the objective to minimize the total cost of C/D wafers. A real‐world example is given to illustrate the practicality of a stochastic approach. The results are better in comparison with deterministic linear programming by using expectation instead of stochastic demands. The model improved the performance of control and dummy wafers management and the flexibility of determining the downgrading policy. Copyright © 2008 John Wiley & Sons, Ltd.     

Control Policy for a Manufacturing System with Random Yield and Rework

We develop a production policy that controls work-in-process (WIP) levels and satisfies demand in a multistage manufacturing system with significant uncertainty in yield, rework, and demand. The problem addressed in this paper is more general than those in the literature in three aspects: (i) multiple products are processed at multiple workstations, and the capacity of each workstation is limited and shared by multiple operations; (ii) the behavior of a production policy is investigated over an infinite-time horizon, and thus the system stability can be evaluated; (iii) the representation of yield and rework uncertainty is generalized. Generalizing both the system structure and the nature of uncertainty requires a new mathematical development in the theory of infinite-horizon stochastic dynamic programming. The theoretical contributions of this paper are the existence proofs of the optimal stationary control for a stochastic dynamic programming problem and the finite covariances of WIP and production levels under the general expression of uncertainty. We develop a simple and explicit sufficient condition that guarantees the existence of both the optimal stationary control and the system stability. We describe how a production policy can be constructed for the manufacturing system based on the propositions derived.     

Optimal stopping of switching diffusions with state dependent switching rates

This paper is concerned with a continuous-time and infinite-horizon optimal stopping problem in switching diffusion models. In contrast to the assumption commonly made in the literature that the regime-switching is modeled by an independent Markov chain, we consider in this paper the case of state-dependent regime-switching. The Hamilton–Jacobi–Bellman (HJB) equation associated with the optimal stopping problem is given by a system of coupled variational inequalities. By means of the dynamic programming (DP) principle, we prove that the value function is the unique viscosity solution of the HJB system. As an interesting application in mathematical finance, we examine the problem of pricing perpetual American put options with state-dependent regime-switching. A numerical procedure is developed based on the DP approach and an efficient discrete tree approximation of the continuous asset price process. Numerical results are reported.     

A stochastic programming approach for planning horizons of infinite horizon capacity planning problems

Planning horizon is a key issue in production planning. Different from previous approaches based on Markov Decision Processes, we study the planning horizon of capacity planning problems within the framework of stochastic programming. We first consider an infinite horizon stochastic capacity planning model involving a single resource, linear cost structure, and discrete distributions for general stochastic cost and demand data (non-Markovian and non-stationary). We give sufficient conditions for the existence of an optimal solution. Furthermore, we study the monotonicity property of the finite horizon approximation of the original problem. We show that, the optimal objective value and solution of the finite horizon approximation problem will converge to the optimal objective value and solution of the infinite horizon problem, when the time horizon goes to infinity. These convergence results, together with the integrality of decision variables, imply the existence of a planning horizon. We also develop a useful formula to calculate an upper bound on the planning horizon. Then by decomposition, we show the existence of a planning horizon for a class of very general stochastic capacity planning problems, which have complicated decision structure.     

Joint pricing and inventory control with a Markovian demand model

We consider the joint pricing and inventory control problem for a single product over a finite horizon and with periodic review. The demand distribution in each period is determined by an exogenous Markov chain. Pricing and ordering decisions are made at the beginning of each period and all shortages are backlogged. The surplus costs as well as fixed and variable costs are state dependent. We show the existence of an optimal (s, S, p)-type feedback policy for the additive demand model. We extend the model to the case of emergency orders. We compute the optimal policy for a class of Markovian demand and illustrate the benefits of dynamic pricing over fixed pricing through numerical examples. The results indicate that it is more beneficial to implement dynamic pricing in a Markovian demand environment with a high fixed ordering cost or with high demand variability.     

Optimal Policies for Production/Inventory Systems with Finite Capacity and Markov-Modulated Demand and Supply Processes

In many production/inventory systems, not only is the production/inventory capacity finite, but the systems are also subject to random production yields that are influenced by factors such as breakdowns, repairs, maintenance, learning, and the introduction of new technologies. In this paper, we consider a single-item, single-location, periodic-review model with finite capacity and Markov modulated demand and supply processes. When demand and supply processes are driven by two independent, discrete-time, finite-state, time-homogeneous Markov chains, we show that a modified, state-dependent, inflated base-stock policy is optimal for both the finite and infinite horizon planning problems. We also show that the finite-horizon solution converges to the infinite-horizon solution.     

Numerical solution of a long-term average control problem for singular stochastic processes

This paper analyzes numerically a long-term average stochastic control problem involving a controlled diffusion on a bounded region. The solution technique takes advantage of an infinite-dimensional linear programming formulation for the problem which relates the stationary measures to the generators of the diffusion. The restriction of the diffusion to an interval is accomplished through reflection at one end point and a jump operator acting singularly in time at the other end point. Different approximations of the linear program are obtained using finite differences for the differential operators (a Markov chain approximation to the diffusion) and using a finite element method to approximate the stationary density. The numerical results are compared with each other and with dynamic programming. This research has been supported in part by the U.S. National Security Agency under Grant Agreement Number H98230-05-1-0062. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation herein.     

A structure of doubly stochastic Markov chains

Kingman and Williams [6] showed that a pattern of positive elements can occur in a transition matrix of a finite state, nonhomogeneous Markov chain if and only if it may be expressed as a finite product of reflexive and transitive patterns. In this paper we solve a similar problem for doubly stochastic chains. We prove that a pattern of positive elements can occur in a transition matrix of a doubly stochastic Markov chain if and only if it may be expressed as a finite product of reflexive, transitive, and symmetric patterns. We provide an algorithm for determining whether a given pattern may be expressed as a finite product of reflexive, transitive, and symmetric patterns. This result has implications for the embedding problem for doubly stochastic Markov chains. We also give the application of the obtained characterization to the chain majorization.     

Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions

In this paper, we consider a capacitated single-level dynamic lot-sizing problem with sequence-dependent setup costs and times that includes product substitution options. The model is motivated from a real-world production planning problem of a manufacturer of plastic sheets used as an interlayer in car windshields. We develop a mixed-integer programming (MIP) formulation of the problem and devise MIP-based Relax&Fix and Fix&Optimize heuristics. Unlike existing literature, we combine Fix&Optimize with a time decomposition. Also, we develop a specialized substitute decomposition and devise a computation budget allocation scheme for ensuring a uniform, efficient usage of computation time by decompositions and their subproblems. Computational experiments were performed on generated instances whose structure follows that of the considered practical application and which have rather tight production capacities. We found that a Fix&Optimize algorithm with an overlapping time decomposition yielded the best solutions. It outperformed the state-of-the-art approach Relax&Fix and all other tested algorithm variants on the considered class of instances, and returned feasible solutions with neither overtime nor backlogging for all instances. It returned solutions that were on average only 5% worse than those returned by a standard MIP solver after 4 hours and 19% better than those of Relax&Fix.