Hierarchical controls in stochastic manufacturing systems with machines in tandem

This paper presents an asymptotic analysis of hierarchical production planning in a manufacturing system with serial machines that are subject to breakdown and repair, and with convex costs. The machines capacities are modeled as Markov chains. Since the number of parts in the internal buffers between any two machines needs to be non-negative, the problem is inherently a state constrained problem. As the rate of change in machines states approaches infinity, the analysis results in a limiting problem in which the stochastic machines capacity is replaced by the equilibrium mean capacity. A method of “lifting” and “modification” is introduced in order to construct near optimal controls for the original problem by using near optimal controls of the limiting problem. The value function of the original problem is shown to converge to the value function of the limiting problem, and the convergence rate is obtained based on some a priori estimates of the asymptotic behavior of the Markov chains. As a result, an error estimate can be obtained on the near optimality of the controls constructed for the original problem.     

Hierarchical Production Control in Dynamic Stochastic Jobshops with Long-Run Average Cost

We consider a production planning problem for a dynamic jobshop producing a number of products and subject to breakdown and repair of machines. The machine capacities are assumed to be finite-state Markov chains. As the rates of change of the machine states approach infinity, an asymptotic analysis of this stochastic manufacturing systems is given. The analysis results in a limiting problem in which the stochastic machine availability is replaced by its equilibrium mean availability. The long-run average cost for the original problem is shown to converge to the long-run average cost of the limiting problem. The convergence rate of the long-run average cost for the original problem to that of the limiting problem together with an error estimate for the constructed asymptotic optimal control is established.     

Hierarchical production policies in stochastic two-machine flowshops with finite buffers

This paper concerns production planning in manufacturing systems with two unreliable machines in tandem. The problem is formulated as a stochastic control problem in which the objective is to minimize the expected total cost of production, inventories, and backlogs. Since the sizes of the internal and external buffers are finite, the problem is one with state constraints. As the optimal solutions to this problem are extremely difficult to obtain due to the uncertainty in machine capacities as well as the presence of state constraints, a deterministic limting problem in which the stochastic machine capacities are replaced by their mean capacities is considered instead. The weak Lipschitz property of the value functions for the original and limiting problems is introduced and proved; a constraint domain approximation approach is developed to show that the value function of the original problem converges to that of the limiting problem as the rate of change in machine states approaches infinity. Asymptotic optimal production policies for the orginal problem are constructed explicity from the near-optimal policies of the limiting problem, and the error estimate for the policies constructed is obtained. Algorithms for constructing these policies are presented.This work was partly supported by CUHK Direct Grant 220500660, RGC Earmarked Grant CUHK 249/94E, and RGC Earmarked Grant CUHK 489/95E.     

A piecewise linear upper bound on the network recourse function

We consider the optimal value of a pure minimum cost network flow problem as a function of supply, demand and arc capacities. We present a new piecewise linear upper bound on this function, which is called the network recourse function. The bound is compared to the standard Madansky bound, and is shown computationally to be a little weaker, but much faster to find. The amount of work is linear in the number of stochastic variables, not exponential as is the case for the Madansky bound. Therefore, the reduction in work increases as the number of stochastic variables increases. Computational results are presented.     

Hierarchical controls in stochastic manufacturing systems with convex costs

This paper presents an extension of earlier research on heirarchical control of stochastic manufacturing systems with linear production costs. A new method is introduced to construct asymptotically optimal open-loop and feedback controls for manufacturing systems in which the rates of machine breakdown and repair are much larger than the rate of fluctuation in demand and rate of discounting of cost. This new approach allows us to carry out an asymptotic analysis on manufacturing systems with convex inventory/backlog and production costs as well as obtain error bound estimates for constructed open loop controls. Under appropriate conditions, an asymptotically optimal Lipschitz feedback control law is obtained.This work was partly supported by the NSERC Grant A4619, URIF, General Motors of Canada, and Manufacturing Research Corporation of Ontario.     

Production and replacement policies for a deteriorating manufacturing system under random demand and quality

This work investigates the production planning of an unreliable deteriorating manufacturing system under uncertainties. The effect of the deterioration phenomenon on the machine is mainly observed in its availability and the quality of the parts produced, with the rates of failure and defectives increasing with the age of the machine. The option to replace the machine should be considered to mitigate the effect of deterioration in order to ensure long-term satisfaction of demand. The objective of this paper is to find the production rate and the replacement policy that minimize the total discounted cost, which includes inventory, backlog, production, repair and replacement costs, over an infinite planning horizon. We formulate the stochastic control problem in the framework of a semi-Markov decision process to consider the machine's history. The integration of random demand and quality behaviour led us to propose a new modeling approach by developing optimality conditions in terms of a second-order approximation of Hamilton–Jacobi–Bellman (HJB) equations. Numerical methods are used to obtain the optimal control policies. Finally, a numerical example and a sensitivity analysis are presented in order to illustrate and confirm the structure of the optimal solution obtained.     

Hierarchical decision making in production and repair/replacement planning with imperfect repairs under uncertainties

In this paper, we analyse an optimal production, repair and replacement problem for a manufacturing system subject to random machine breakdowns. The system produces parts, and upon machine breakdown, either an imperfect repair is undertaken or the machine is replaced with a new identical one. The decision variables of the system are the production rate and the repair/replacement policy. The objective of the control problem is to find decision variables that minimize total incurred costs over an infinite planning horizon. Firstly, a hierarchical decision making approach, based on a semi-Markov decision model (SMDM), is used to determine the optimal repair and replacement policy. Secondly, the production rate is determined, given the obtained repair and replacement policy. Optimality conditions are given and numerical methods are used to solve them and to determine the control policy. We show that the number of parts to hold in inventory in order to hedge against breakdowns must be readjusted to a higher level as the number of breakdowns increases or as the machine ages. We go from the traditional policy with only one high threshold level to a policy with several threshold levels, which depend on the number of breakdowns. Numerical examples and sensitivity analyses are presented to illustrate the usefulness of the proposed approach.     

On rates of convergence and asymptotic normality in the multiknapsack problem

In Meanti et al. (1990) an almost sure asymptotic characterization has been derived for the optimal solution value as function of the knapsack capacities, when the profit and requirement coefficients of items to be selected from are random variables. In this paper we establish a rate of convergence for this process using results from the theory of empirical processes.     

Asymptotic behavior of continuous stochastic games

Summary The aim of this paper is to analyze the asymptotic behavior of the value functions of a continuous stochastic game as the number of stages grows to infinity or the discount factor approaches 1. After the setup of the problem we prove that, in both cases, the extrema of the value functions converge to the same limits. The convergence of the value functions is then obtained from the unicity of the solution of a functional problem and it is thus possible to design hypotheses that assure the convergence to a constant. This allows to assign a value to an undiscounted infinite-stage stochastic game in several senses and to show that optimal strategies are available for both players. Furthermore the boundedness of the remainders of the value function after removing the principal terms is analyzed, with appropriate hypotheses, and related to the existence of solutions of a Howard's type functional equation. This allows to show that for an infinite-stage undiscounted stochastic game optimal stationary strategies exist at least if this functional equation has some solution.     

An optimal portfolio model with stochastic volatility and stochastic interest rate

We consider a portfolio optimization problem under stochastic volatility as well as stochastic interest rate on an infinite time horizon. It is assumed that risky asset prices follow geometric Brownian motion and both volatility and interest rate vary according to ergodic Markov diffusion processes and are correlated with risky asset price. We use an asymptotic method to obtain an optimal consumption and investment policy and find some characteristics of the policy depending upon the correlation between the underlying risky asset price and the stochastic interest rate.     

Optimal deteriorating items production inventory models with random machine breakdown and stochastic repair time

This study develops deteriorating items production inventory models with random machine breakdown and stochastic repair time. The model assumes the machine repair time is independent of the machine breakdown rate. The classical optimization technique is used to derive an optimal solution. A numerical example and sensitivity analysis are shown to illustrate the models. The stochastic repair models with uniformly distributed repair time tends to have a larger optimal total cost than the fixed repair time model, however the production up time is less than the fixed repair time model. Production and demand rate are the most sensitive parameters for the optimal production up time, and demand rate is the most sensitive parameter to the optimal total cost for the stochastic model with exponential distribution repair time.     

Optimal liquidation under partial information with price impact

We study the optimal liquidation problem in a market model where the bid price follows a geometric pure jump process whose local characteristics are driven by an unobservable finite-state Markov chain and by the liquidation rate. This model is consistent with stylized facts of high frequency data such as the discrete nature of tick data and the clustering in the order flow. We include both temporary and permanent effects into our analysis. We use stochastic filtering to reduce the optimal liquidation problem to an equivalent optimization problem under complete information. This leads to a stochastic control problem for piecewise deterministic Markov processes (PDMPs). We carry out a detailed mathematical analysis of this problem. In particular, we derive the optimality equation for the value function, we characterize the value function as continuous viscosity solution of the associated dynamic programming equation, and we prove a novel comparison result. The paper concludes with numerical results illustrating the impact of partial information and price impact on the value function and on the optimal liquidation rate.     

Time Discretisation and Rate of Convergence for the Optimal Control of Continuous-Time Stochastic Systems with Delay

We study a semi-discretisation scheme for stochastic optimal control problems whose dynamics are given by controlled stochastic delay (or functional) differential equations with bounded memory. Performance is measured in terms of expected costs. By discretising time in two steps, we construct a sequence of approximating finite-dimensional Markovian optimal control problems in discrete time. The corresponding value functions converge to the value function of the original problem, and we derive an upper bound on the discretisation error or, equivalently, a worst-case estimate for the rate of convergence.     

Optimal design of unreliable production–inventory systems with variable production rate

In this article, we study an economic manufacturing quantity (EMQ) problem for an unreliable production facility where the production rate is treated as a decision variable. As the stress condition of the machine changes with the production rate, the failure rate of the machine is assumed to be dependent on the production rate. The unit production cost is also taken as a function of the production rate, as the machine can be operated at different production rates resulting in different unit production costs. The basic EMQ model is formulated under general failure and general repair time distributions and the optimal production policy is derived for specific failure and repair time distributions viz., exponential failure and exponential repair time distributions. Considering randomness of the time to machine failure and corrective repair time, the model is extended to the case where certain safety stocks in inventory may be useful to improve service level to customers. Optimal production policies of the proposed models are derived numerically and the sensitivity of the optimal results with respect to those parameters which directly influence the machine failure and repair rates is also examined.     

Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic

We address a rate control problem associated with a single server Markovian queueing system with customer abandonment in heavy traffic. The controller can choose a buffer size for the queueing system and also can dynamically control the service rate (equivalently the arrival rate) depending on the current state of the system. An infinite horizon cost minimization problem is considered here. The cost function includes a penalty for each rejected customer, a control cost related to the adjustment of the service rate and a penalty for each abandoning customer. We obtain an explicit optimal strategy for the limiting diffusion control problem (the Brownian control problem or BCP) which consists of a threshold-type optimal rejection process and a feedback-type optimal drift control. This solution is then used to construct an asymptotically optimal control policy, i.e. an optimal buffer size and an optimal service rate for the queueing system in heavy traffic. The properties of generalized regulator maps and weak convergence techniques are employed to prove the asymptotic optimality of this policy. In addition, we identify the parameter regimes where the infinite buffer size is optimal.     

Numerical approximation of connecting orbits with asymptotic rate

Summary. In this paper we set up and analyze a numerical method for so called {\bf connecting orbits with asymptotic rate } in parameterized dynamical systems. A connecting orbit with asymptotic rate has its initial value in a given submanifold of the phase space (or its cross product with parameter space) and it converges with an exponential rate to a given orbit, e. g. a steady state or a periodic orbit. It is well known that orbits with asymptotic rate can be used to foliate stable or strong stable manifolds of invariant sets. We show that the problem of determining a connecting orbit with asymptotic rate is well-posed if a certain transversality condition is made and a specific relation between the number of stable dimensions and the number of parameters holds. For the proof we employ the implicit function theorem in spaces of exponentially decaying functions. Using asymptotic boundary conditions we truncate the original problem to a finite interval and show that the error decays exponentially. Typically the asymptotic boundary conditions by themselves are the result of a boundary value problem, e. g. if the limiting orbit is periodic. Thus it is expensive to calculate them in a parameter dependent way during the approximation procedure. To avoid this we develop a boundary corrector method which turns out to be nearly optimal after very few steps. Received April 28, 2000 / Revised version received December 18, 2000 / Published online May 30, 2001     

Stochastic recursive inclusions with non-additive iterate-dependent Markov noise

In this paper we study the asymptotic behaviour of stochastic approximation schemes with set-valued drift function and non-additive iterate-dependent Markov noise. We show that a linearly interpolated trajectory of such a recursion is an asymptotic pseudotrajectory for the flow of a limiting differential inclusion obtained by averaging the set-valued drift function of the recursion w.r.t. the stationary distributions of the Markov noise. The limit set theorem by Benaim is then used to characterize the limit sets of the recursion in terms of the dynamics of the limiting differential inclusion. We then state two variants of the Markov noise assumption under which the analysis of the recursion is similar to the one presented in this paper. Scenarios where our recursion naturally appears are presented as applications. These include controlled stochastic approximation, subgradient descent, approximate drift problem and analysis of discontinuous dynamics all in the presence of non-additive iterate-dependent Markov noise.     

The Concavity Assumption on Felicities and Asymptotic Dynamics in the RSS Model

An analysis of the RSS model in mathematical economics involves the study of an infinite-horizon variational problem in discrete time. Under the assumption that the felicity function is upper semicontinuous and “supported” at the value of the maximally-sustainable level of a production good, we report a generalization of results on the equivalence, existence and asymptotic convergence of optimal trajectories in this model. We consider two parametric specifications, and under the second, identify a “symmetry” condition on the zeroes of a “discrepancy function” underlying the objective function that proves to be necessary and sufficient for the asymptotic convergence of good programs. With a concave objective function, as is standard in the antecedent literature, we show that the symmetry condition reduces to an equivalent “non-interiority” condition.     

Admission policies for the customized stochastic lot scheduling problem with strict due-dates

This papers considers admission control and scheduling of customer orders in a production system that produces different items on a single machine. Customer orders drive the production and belong to product families, and have family dependent due-date, size, and reward. When production changes from one family to another a setup time is incurred. Moreover, if an order cannot be accepted, it is considered lost upon arrival. The problem is to find a policy that accepts/rejects and schedules orders such that long run profit is maximized. This problem finds its motivation in batch industries in which suppliers have to realize high machine utilization while delivery times should be short and reliable and the production environment is subject to long setup times.We model the joint admission control/scheduling problem as a Markov decision process (MDP) to gain insight into the optimal control of the production system and use the MDP to benchmark the performance of a simple heuristic acceptance/scheduling policy. Numerical results show that the heuristic performs very well compared with the optimal policy for a wide range of parameter settings, including product family asymmetries in arrival rate, order size, and order reward.     

A branch and bound method for stochastic global optimization

A stochastic branch and bound method for solving stochastic global optimization problems is proposed. As in the deterministic case, the feasible set is partitioned into compact subsets. To guide the partitioning process the method uses stochastic upper and lower estimates of the optimal value of the objective function in each subset. Convergence of the method is proved and random accuracy estimates derived. Methods for constructing stochastic upper and lower bounds are discussed. The theoretical considerations are illustrated with an example of a facility location problem.