Zero-Inventory Conditions for a Two-Part-Type Make-to-Stock Production System

We consider the dynamic scheduling of a two-part-type make-to-stock production system using the model of Wein [12]. Exogenous demand for each part type is met from finished goods inventory; unmet demand is backordered. The control policy determines which part type, if any, to produce at each moment; complete flexibility is assumed. The objective is to minimize average holding and backorder costs. For exponentially distributed interarrival and production times, necessary and sufficient conditions are found for a zero-inventory policy to be optimal. This result indicates the economic and production conditions under which a simple make-to-order control is optimal. Weaker results are given for the case of general production times.     

On optimal polling policies

In a single-server polling system, the server visits the queues according to a routing policy and while at a queue, serves some or all of the customers there according to a service policy. A polling (or scheduling) policy is a sequence of decisions on whether to serve a customer, idle the server, or switch the server to another queue. The goal of this paper is to find polling policies that stochastically minimize the unfinished work and the number of customers in the system at all times. This optimization problem is decomposed into three subproblems: determine the optimal action (i.e., serve, switch, idle) when the server is at a nonempty queue; determine the optimal action (i.e., switch, idle) when the server empties a queue; determine the optimal routing (i.e., choice of the queue) when the server decides to switch. Under fairly general assumptions, we show for the first subproblem that optimal policies are greedy and exhaustive, i.e., the server should neither idle nor switch when it is at a nonempty queue. For the second subproblem, we prove that in symmetric polling systems patient policies are optimal, i.e., the server should stay idling at the last visited queue whenever the system is empty. When the system is slotted, we further prove that non-idling and impatient policies are optimal. For the third subproblem, we establish that in symmetric polling systems optimal policies belong to the class of Stochastically Largest Queue (SLQ) policies. An SLQ policy is one that never routes the server to a queue known to have a queue length that is stochastically smaller than that of another queue. This result implies, in particular, that the policy that routes the server to the queue with the largest queue length is optimal when all queue lengths are known and that the cyclic routing policy is optimal in the case that the only information available is the previous decisions.This work was supported in part by NSF under Contract ASC-8802764.     

Asymptotically optimal open-loop load balancing

In many distributed computing systems, stochastically arriving jobs need to be assigned to servers with the objective of minimizing waiting times. Many existing dispatching algorithms are basically included in the SQ(d) framework: Upon arrival of a job, \(d\ge 2\) servers are contacted uniformly at random to retrieve their state and then the job is routed to a server in the best observed state. One practical issue in this type of algorithm is that server states may not be observable, depending on the underlying architecture. In this paper, we investigate the assignment problem in the open-loop setting where no feedback information can flow dynamically from the queues back to the controller, i.e., the queues are unobservable. This is an intractable problem, and unless particular cases are considered, the structure of an optimal policy is not known. Under mild assumptions and in a heavy-traffic many-server limiting regime, our main result proves the optimality of a subset of deterministic and periodic policies within a wide set of (open-loop) policies that can be randomized or deterministic and can be dependent on the arrival process at the controller. The limiting value of the scaled stationary mean waiting time achieved by any policy in our subset provides a simple approximation for the optimal system performance.     

Optimal due-date determination and sequencing with random processing times

This paper considers the problem of due-date determination and sequencing of n stochastically independent jobs on a single machine with random processing times. The objective is to find the optimal due-date values for the constant due-date assignment method and the optimal job sequence that minimize the expected value of a total cost function. It is shown that under suitable assumptions the optimal due-date values can be analytically determined and the jobs should be arranged in the SEPT sequence to minimize the cost.     

Optimality of routing and servicing in dependent parallel processing systems

In a system of dependent, parallel processing service stations, when is it optimal to route customers to the shortest queue and to devote auxiliary capacity to serve the longest queue? We show that this RSQ/SLQ policy is optimal for a wide class of Markovian systems, where the arrival and service rates at the stations, which may depend on the numbers of customers at all the stations, satisfy certain symmetry and monotonicity conditions. Under this policy, the queue lengths will be stochastically smaller in the weak submajorization ordering than the queue lengths under any other policy. Furthermore, this policy minimizes standard discounted and average cost functionals over finite and infinite horizons.     

Optimizing costs of age replacement policies

This paper continues earlier work on the best implementation procedure for an age replacement policy. Under an age replacement policy, a stochastically failing unit is replaced at failure or after being in service for x units of time, whichever comes first. Sequentially estimating φ, the optimal replacement time, produces substantial cost savings. In this paper the rate of convergence of the actual costs to the theoretical optimal cost is studied. For any sequential procedure satisfying some mild measurability conditions, it is shown that with probability one the rate of convergence of the cost can be described based on the rate of convergence of the estimator of φ. Further, a sequential procedure is described whose cost converges to the optimal cost more rapidly than known competing procedures. For this procedure, the rate of convergence of the costs is further described by a result which states that an average actual cost per unit, when suitably standardized, converges in distribution to a normal random variable.     

A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties

In this paper, a hybrid genetic algorithm is developed to solve the single machine scheduling problem with the objective to minimize the weighted sum of earliness and tardiness costs. First, dominance properties of (the conditions on) the optimal schedule are developed based on the switching of two adjacent jobs i and j. These dominance properties are only necessary conditions and not sufficient conditions for any given schedule to be optimal. Therefore, these dominance properties are further embedded in the genetic algorithm and we call it genetic algorithm with dominance properties (GADP). This GADP is a hybrid genetic algorithm. The initial populations of schedules in the genetic algorithm are generated using these dominance properties. GA can further improve the performance of these initial solutions after the evolving procedures. The performances of hybrid genetic algorithm (GADP) have been compared with simple genetic algorithm (SGA) using benchmark instances. It is shown that this hybrid genetic algorithm (GADP) performs very well when compared with DP or SGA alone.     

An optimal replacement policy for a multistate degenerative simple system

In this paper, a degenerative simple system (i.e. a degenerative one-component system with one repairman) with k + 1 states, including k failure states and one working state, is studied. Assume that the system after repair is not “as good as new”, and the degeneration of the system is stochastic. Under these assumptions, we consider a new replacement policy T based on the system age. Our problem is to determine an optimal replacement policy T^∗ such that the average cost rate (i.e. the long-run average cost per unit time) of the system is minimized. The explicit expression of the average cost rate is derived, the corresponding optimal replacement policy can be determined, the explicit expression of the minimum of the average cost rate can be found and under some mild conditions the existence and uniqueness of the optimal policy T^∗ can be proved, too. Further, we can show that the repair model for the multistate system in this paper forms a general monotone process repair model which includes the geometric process repair model as a special case. We can also show that the repair model in the paper is equivalent to a geometric process repair model for a two-state degenerative simple system in the sense that they have the same average cost rate and the same optimal policy. Finally, a numerical example is given to illustrate the theoretical results of this model.     

Dynamic control of a flexible server in an assembly-type queue with setup costs

We consider a queueing system with multiple stations attended by a single flexible server. An order arriving at this system needs to go through each station only once but there is no particular precedence relationship among these stations. One can also think of this system as an assembly system where each station processes a different component of an order and once all the components associated with an order are processed they are assembled instantaneously. A holding cost is charged for keeping the orders in the system and there is a penalty associated with the switches of the server between stations. Our objective is to minimize the long-run average costs by dynamically assigning the server to stations based on the system state. Using sample-path arguments, we provide partial characterizations of the optimal policy and provide sufficient conditions under which a simple state-independent policy that works on one order at a time is optimal. We also propose three simple threshold policies and present a numerical study that provides supporting evidence for the superior performance of our double-threshold heuristic.     

Joint-optimization of inventory policies on a multi-product multi-echelon pharmaceutical system with batching and ordering constraints

This paper presents a methodology to find near-optimal joint inventory control policies for the real case of a one-warehouse, n-retailer distribution system of infusion solutions at a University Medical Center in France. We consider stochastic demand, batching and order-up-to level policies as well as aspects particular to the healthcare setting such as emergency deliveries, required service level rates and a new constraint on the ordering policy that fits best the hospital’s interests instead of abstract ordering costs. The system is modeled as a Markov chain with an objective to minimize the stock-on-hand value for the overall system. We provide the analytical structure of the model to show that the optimal reorder point of the policy at both echelons is easily derived from a simple probability calculation. We also show that the optimal policy at the care units is to set the order-up-to level one unit higher than the reorder point. We further demonstrate that optimizing the care units in isolation is optimal for the joint multi-echelon, n-retailer problem. A heuristic algorithm is presented to find the near-optimal order-up-to level of the policy of each product at the central pharmacy; all other policy parameters are guaranteed optimal via the structure provided by the model. Comparison of our methodology versus that currently in place at the hospital showed a reduction of approximately 45% in the stock-on-hand value while still respecting the service level requirements.     

Effect of Modeling Uncertainty on Some Routing Problems

In this paper, we consider the routing problem described in Mohanty and Cassandras (Ref. 1). As in Ref. 1, we show that the optimal Bernoulli split to minimize mean time in the system is asymptotically independent of the variance of the service time. We give simple proofs of the results in that paper. We exploit the fact that the optimal split to minimize the mean queueing time is variance independent and the special structure of the Karush–Kuhn–Tucker optimality conditions to derive the optimal solution. Apart from being very straightforward, the proofs also give insight into the reason for the existence of the variance-independent asymptotically optimal routing policy.     

Sourcing from suppliers with random yield for price-dependent demand

We study a multi-period inventory planning problem. In each period, the firm under consideration can source from two possibly unreliable suppliers for a price-dependent demand. Our analysis suggests that the optimal procurement policy is neither a simple reorder-point policy nor a complex one without any structure, as previous studies suggest. Instead, we prove the existence of a reorder point for each supplier. No order is placed to that supplier for any inventory level above the reorder point and a positive order is issued to that supplier for almost every inventory level below the reorder point. We characterize conditions under which the optimal policy reveals monotone response to changes in the inventory level. Furthermore, two special cases of our model are examined in detail to demonstrate how our analysis generalizes a number of well-known results in the literature.     

Dynamic admission and service rate control of a queue

This paper investigates a queueing system in which the controller can perform admission and service rate control. In particular, we examine a single-server queueing system with Poisson arrivals and exponentially distributed services with adjustable rates. At each decision epoch the controller may adjust the service rate. Also, the controller can reject incoming customers as they arrive. The objective is to minimize long-run average costs which include: a holding cost, which is a non-decreasing function of the number of jobs in the system; a service rate cost c(x), representing the cost per unit time for servicing jobs at rate x; and a rejection cost κ for rejecting a single job. From basic principles, we derive a simple, efficient algorithm for computing the optimal policy. Our algorithm also provides an easily computable bound on the optimality gap at every step. Finally, we demonstrate that, in the class of stationary policies, deterministic stationary policies are optimal for this problem.     

Optimal replacement policy for a deteriorating system with increasing repair times

This paper considers an optimal maintenance policy for a practical and reparable deteriorating system subject to random shocks. Modeling the repair time by a geometric process and the failure mechanism by a generalized δ-shock process, we develop an explicit expression of the long-term average cost per time unit for the system under a threshold-type replacement policy. Based on this average cost function, we propose a finite search algorithm to locate the optimal replacement policy N^∗ to minimize the average cost rate. We further prove that the optimal policy N^∗ is unique and present some numerical examples. Many practical systems fit the model developed in this paper.     

A duality approach to admission and scheduling controls of queues

This paper studies theadmission andscheduling control problem in anM/M/2 queueing system with nonidentical processors. Admission control renders when a newly arrived job should be accepted, whereas scheduling control determines when an available processor should be utilized. The system received a rewardR when a job completes its service and pays a unit holding costC while a job is in the system. The main goal of the paper is to obtain the admission/scheduling policy that maximizes the expected discounted and long-run average profits (reward minus cost). We convert the system into its dual, a stochastically identical system subject toexpulsion/scheduling control, and prove that the individually optimal policy in the dual system is socially optimal in the original system. In contrast with the dynamic programming (DP) technique which considers the system as a whole, we adopt the viewpoint of an individual job and analyze the impact of its behavior on the social outcome. The key properties which simplify the analysis are that under the individually optimal policy the profit of a job under the preemptive last-come first-priority service discipline (LCFP-P) is independent of jobs arrived earlier than itself and that the system is insensitive to service discipline imposed. The former makes possible to bypass complex dynamic programming analyses and the latter serves as a vehicle in connecting the social and individual optimality. We also exploit system operational characteristics under LCFP-P to obtain simple and close approximations of the optimal thresholds.     

Controlling arrivals for a queueing system with an unreliable server: Newton-Quasi method

This paper deals with the control policy of a removable and unreliable server for an M/M/1/K queueing system, where the removable server operates an F-policy. The so-called F-policy means that when the number of customers in the system reaches its capacity K (i.e. the system becomes full), the system will not accept any incoming customers until the queue length decreases to a certain threshold value F. At that time, the server initiates an exponential startup time with parameter γ and starts allowing customers entering the system. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. A matrix analytical method is applied to derive the steady-state probabilities through which various system performance measures can be obtained. A cost model is constructed to determine the optimal values, say (F^∗, μ^∗, γ^∗), that yield the minimum cost. Finally, we use the two methods, namely, the direct search method and the Newton-Quasi method to find the global minimum (F^∗, μ^∗, γ^∗). Numerical results are also provided under optimal operating conditions.     

Optimal ordering policies with convertible lead times

A firm receives orders that will be required at an uncertain time given by an Erlang distribution, and over time observes the associated independent exponential events. The firm, in turn, places orders at a linear cost from a supplier with fixed lead time l and has the option of converting (expediting) each order, at a cost, over a certain time interval after the order is originally placed. A converted order arrives l_e < l units of time after it is converted. We show that a threshold policy is optimal. Under such a policy the firm places an order after a certain number of exponential events have been observed. An order is converted the first time, if any, when the residual lead time exceeds a time threshold related to the number of exponential events realized since the order was placed.     

Basic optimality results for Bayesian group replacement policies

The optimal structure of Bayesian group replacement policies for a parallel system of n items with exponential failure times and random failure parameter is presented. The paper contains a proof of the fact that it is optimal to observe the system only at failure times. For the case of two items operating in parallel the exact form of the policy is derived.     

A simple procedure for determining order quantities under a fill rate constraint and normally distributed lead-time demand

One of the most common practical inventory control problems is considered. A single-echelon inventory system is controlled by a continuous review (R, Q) policy. The lead-time demand is normally distributed. We wish to minimize holding and ordering costs under a fill rate constraint. Although, it is not especially complicated to derive the optimal solution, it is much more common in practice to use a simple approximate two-step procedure where the order quantity is determined from a deterministic model in the first step. We provide an alternative, equally simple technique, which is based on the observation that the considered problem for each considered fill rate has a single parameter only. The optimal solution for a grid of parameter values is stored in a file. When solving the problem for an item we use interpolation, or for parameter values outside the grid special approximations. The approximation errors turn out to be negligible. As an alternative to the interpolation we also provide polynomial approximations.