Quantifying the performance effects of idle time utilization in multiserver systems

In many practical multiserver queueing systems, servers not only serve randomly arriving customers but also work on the secondary jobs with infinite backlog during their idle time. In this paper, we propose a c‐server model with a two‐threshold policy, denoted by (e d), to evaluate the performance of this class of systems. With such a policy, when the number of idle servers has reached d (<c), then e (<d) idle agents will process secondary jobs. These e servers keep working on the secondary jobs until they find waiting customers exist in the system at a secondary job completion instant. Using the matrix analytic method, we obtain the stationary performance measures for evaluating different (e, d) policies. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Exact analysis of (R,s, S) inventory control systems with lost sales and zero lead time

We study an (R, s, S) inventory control policy with stochastic demand, lost sales, zero lead‐time and a target service level to be satisfied. The system is modeled as a discrete time Markov chain for which we present a novel approach to derive exact closed‐form solutions for the limiting distribution of the on‐hand inventory level at the end of a review period, given the reorder level (s) and order‐up‐to level (S). We then establish a relationship between the limiting distributions for adjacent values of the reorder point that is used in an efficient recursive algorithm to determine the optimal parameter values of the (R, s, S) replenishment policy. The algorithm is easy to implement and entails less effort than solving the steady‐state equations for the corresponding Markov model. Point‐of‐use hospital inventory systems share the essential characteristics of the inventory system we model, and a case study using real data from such a system shows that with our approach, optimal policies with significant savings in inventory management effort are easily obtained for a large family of items.     

An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system

A single server is faced with a collection of jobs of varying duration and urgency. Each job has a random lifetime during which it is available for nonpreemptive service. Should a job's lifetime expire before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximize the expected number served to completion. Two heuristics have been proposed in the literature. One (labeled π^S) operates a static priority among the job classes and works well in a “no premature job loss” limit, whereas the second (π^M) is a myopic heuristic which works well when lifetimes are short. Both can exhibit poor performance for problems at some distance from the regimes for which they were designed. We develop a robustly good heuristic by an approximative approach to the application of a policy improvement step to the asymptotically optimal heuristic π^S, in which we use a fluid model to obtain an approximation for the value function of π^S. The performance of the proposed heuristic is investigated in an extensive numerical study. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

Batch scheduling on a two‐machine jobshop with machine‐dependent setup times

The problem of minimum makespan on an m machine jobshop with unit execution time (UET) jobs (m ≥ 3) is known to be strongly NP‐hard even with no setup times. We focus in this article on the two‐machine case. We assume UET jobs and consider batching with batch availability and machine‐dependent setup times. We introduce an efficient \begin{align*}(O(\sqrt{n}))\end{align*} algorithm, where n is the number of jobs. We then introduce a heuristic for the multimachine case and demonstrate its efficiency for two interesting instances. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Optimal pricing and inventory control policy in periodic‐review systems with fixed ordering cost and lost sales

This paper studies a periodic‐review pricing and inventory control problem for a retailer, which faces stochastic price‐sensitive demand, under quite general modeling assumptions. Any unsatisfied demand is lost, and any leftover inventory at the end of the finite selling horizon has a salvage value. The cost component for the retailer includes holding, shortage, and both variable and fixed ordering costs. The retailer's objective is to maximize its discounted expected profit over the selling horizon by dynamically deciding on the optimal pricing and replenishment policy for each period. We show that, under a mild assumption on the additive demand function, at the beginning of each period an (s,S) policy is optimal for replenishment, and the value of the optimal price depends on the inventory level after the replenishment decision has been done. Our numerical study also suggests that for a sufficiently long selling horizon, the optimal policy is almost stationary. Furthermore, the fixed ordering cost (K) plays a significant role in our modeling framework. Specifically, any increase in K results in lower s and higher S. On the other hand, the profit impact of dynamically changing the retail price, contrasted with a single fixed price throughout the selling horizon, also increases with K. We demonstrate that using the optimal policy values from a model with backordering of unmet demands as approximations in our model might result in significant profit penalty. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Periodic review inventory management with contingent use of two freight modes with fixed costs

We study a stochastic inventory model of a firm that periodically orders a product from a make‐to‐order manufacturer. Orders can be shipped by a combination of two freight modes that differ in lead‐times and costs, although orders are not allowed to cross. Placing an order as well as each use of each freight mode has a fixed and a quantity proportional cost. The decision of how to allocate units between the two freight modes utilizes information about demand during the completion of manufacturing. We derive the optimal freight mode allocation policy, and show that the optimal policy for placing orders is not an (s,S) policy in general. We provide tight bounds for the optimal policy that can be calculated by solving single period problems. Our analysis enables insights into the structure of the optimal policy specifying the conditions under which it simplifies to an (s,S) policy. We characterize the best (s,S) policy for our model, and through extensive numerical investigation show that its performance is comparable with the optimal policy in most cases. Our numerical study also sheds light on the benefits of the dual freight model over the single freight models. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria

We consider the problem of scheduling a set of jobs on a single machine subject to random breakdowns. We focus on the preemptive‐repeat model, which addresses the situation where, if a machine breaks down during the processing of a job, the work done on the job prior to the breakdown is lost and the job will have to be started from the beginning again when the machine resumes its work. We allow that (i) the uptimes and downtimes of the machine follow general probability distributions, (ii) the breakdown process of the machine depends upon the job being processed, (iii) the processing times of the jobs are random variables following arbitrary distributions, and (iv) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We first derive the optimal policy for a class of problems under the criterion to maximize the expected discounted reward earned from completing all jobs. The result is then applied to further obtain the optimal policies for other due date‐related criteria. We also discuss a method to compute the moments and probability distributions of job completion times by using their Laplace transforms, which can convert a general stochastic scheduling problem to its deterministic equivalent. The weighted squared flowtime problem and the maintenance checkup and repair problem are analyzed as applications. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Markovian approximation for manufacturing systems of unreliable machines in tandem

This paper studies production planning of manufacturing systems of unreliable machines in tandem. The manufacturing system considered here produces one type of product. The demand is assumed to be a Poisson process and the processing time for one unit of product in each machine is exponentially distributed. A broken machine is subject to a sequence of repairing processes. The up time and the repairing time in each phase are assumed to be exponentially distributed. We study the manufacturing system by considering each machine as an individual system with stochastic supply and demand. The Markov Modulated Poisson Process (MMPP) is applied to model the process of supply. Numerical examples are given to demonstrate the accuracy of the proposed method. We employ (s, S) policy as production control. Fast algorithms are presented to solve the average running costs of the machine system for a given (s, S) policy and hence the approximated optimal (s, S) policy. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 65–78, 2001     

Optimal maintenance policies for a safety‐critical system and its deteriorating sensor

We consider the integrated problem of optimally maintaining an imperfect, deteriorating sensor and the safety‐critical system it monitors. The sensor's costless observations of the binary state of the system become less informative over time. A costly full inspection may be conducted to perfectly discern the state of the system, after which the system is replaced if it is in the out‐of‐control state. In addition, a full inspection provides the opportunity to replace the sensor. We formulate the problem of adaptively scheduling full inspections and sensor replacements using a partially observable Markov decision process (POMDP) model. The objective is to minimize the total expected discounted costs associated with system operation, full inspection, system replacement, and sensor replacement. We show that the optimal policy has a threshold structure and demonstrate the value of coordinating system and sensor maintenance via numerical examples. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 399–417, 2017     

Machine scheduling with an availability constraint and job delivery coordination

In this paper we study the scheduling problem that considers both production and job delivery at the same time with machine availability considerations. Only one vehicle is available to deliver jobs in a fixed transportation time to a distribution center. The vehicle can load at most K jobs as a delivery batch in one shipment due to the vehicle capacity constraint. The objective is to minimize the arrival time of the last delivery batch to the distribution center. Since machines may not always be available over the production period in real life due to preventive maintenance, we incorporate machine availability into the models. Three scenarios of the problem are studied. For the problem in which the jobs are processed on a single machine and the jobs interrupted by the unavailable machine interval are resumable, we provide a polynomial algorithm to solve the problem optimally. For the problem in which the jobs are processed on a single machine and the interrupted jobs are nonresumable, we first show that the problem is NP‐hard. We then propose a heuristic with a worst‐case error bound of 1/2 and show that the bound is tight. For the problem in which the jobs are processed on either one of two parallel machines, where only one machine has an unavailable interval and the interrupted jobs are resumable, we propose a heuristic with a worst‐case error bound of 2/3. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Newsvendor bounds and heuristics for serial supply chains with regular and expedited shipping

We study an infinite‐horizon, N‐stage, serial production/inventory system with two transportation modes between stages: regular shipping and expedited shipping. The optimal inventory policy for this system is a top–down echelon base‐stock policy, which can be computed through minimizing 2N nested convex functions recursively (Lawson and Porteus, Oper Res 48 (2000), 878–893). In this article, we first present some structural properties and comparative statics for the parameters of the optimal inventory policies, we then derive simple, newsvendor‐type lower and upper bounds for the optimal control parameters. These results are used to develop near optimal heuristic solutions for the echelon base‐stock policies. Numerical studies show that the heuristic performs well. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Single batch machine scheduling with deliveries

We consider the problem of scheduling a set of n jobs on a single batch machine, where several jobs can be processed simultaneously. Each job j has a processing time p_j and a size s_j. All jobs are available for processing at time 0. The batch machine has a capacity D. Several jobs can be batched together and processed simultaneously, provided that the total size of the jobs in the batch does not exceed D. The processing time of a batch is the largest processing time among all jobs in the batch. There is a single vehicle available for delivery of the finished products to the customer, and the vehicle has capacity K. We assume that K = rD, where and r is an integer. The travel time of the vehicle is T; that is, T is the time from the manufacturer to the customer. Our goal is to find a schedule of the jobs and a delivery plan so that the service span is minimized, where the service span is the time that the last job is delivered to the customer. We show that if the jobs have identical sizes, then we can find a schedule and delivery plan in time such that the service span is minimum. If the jobs have identical processing times, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most 11/9 times the optimal service span. When the jobs have arbitrary processing times and arbitrary sizes, then we can find a schedule and delivery plan in time such that the service span is asymptotically at most twice the optimal service span. We also derive upper bounds of the absolute worst‐case ratios in both cases. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 470–482, 2015     

CON/SLK due date assignment and scheduling on a single machine with two agents

We consider scheduling problems involving two agents (agents A and B), each having a set of jobs that compete for the use of a common machine to process their respective jobs. The due dates of the A‐jobs are decision variables, which are determined by using the common (CON) or slack (SLK) due date assignment methods. Each agent wants to minimize a certain performance criterion depending on the completion times of its jobs only. Under each due date assignment method, the criterion of agent A is always the same, namely an integrated criterion consisting of the due date assignment cost and the weighted number of tardy jobs. Several different criteria are considered for agent B, including the maxima of regular functions (associated with each job), the total (weighted) completion time, and the weighted number of tardy jobs. The overall objective is to minimize the performance criterion of agent A, while keeping the objective value of agent B no greater than a given limit. We analyze the computational complexity, and devise polynomial or pseudo‐polynomial dynamic programming algorithms for the considered problems. We also convert, if viable, any of the devised pseudopolynomial dynamic programming algorithms into a fully polynomial‐time approximation scheme. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 416–429, 2016     

Optimal lot sizing and inspection policy for an EMQ model with imperfect inspections

An EMQ model with a production process subject to random deterioration is considered. The process can be monitored through inspections, and both the lot size and the inspection schedule are subject to control. The “in-control” periods are assumed to be generally distributed and the inspections are imperfect, i.e., the true state of the process is not necessarily revealed through an inspection. The objective is the joint determination of the lot size and the inspection schedule, minimizing the long-run expected average cost per unit time. Both discrete and continuous cases are examined. A dynamic programming formulation is considered in the case where the inspections can be performed only at discrete times, which is typical for the parts industry. In the continuous case, an optimum inspection schedule is obtained for a given production time and given number of inspections by solving a nonlinear programming problem. A two-dimensional search procedure can be used to find the optimal policy. In the exponential case, the structure of the optimal inspection policy is established using Lagrange's method, and it is shown that the optimal inspection times can be found by solving a nonlinear equation. Numerical studies indicate that the optimal policy performs much better than the optimal policy with periodic inspections considered previously in the literature. The case of perfect inspections is discussed, and an extension of the results obtained previously in the literature is presented. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 165–186, 1998     

Scheduling deteriorating jobs to minimize makespan

We consider a single-machine problem of scheduling n independent jobs to minimize makespan, in which the processing time of job J_j grows by w_j with each time unit its start is delayed beyond a given common critical date d. This processing time is p_j if J_j starts by d. We show that this problem is NP-hard, give a pseudopolynomial algorithm that runs in time and O(nd) space, and develop a branch-and-bound algorithm that solves instances with up to 100 jobs in a reasonable amount of time. We also introduce the case of bounded deterioration, where the processing time of a job grows no further if the job starts after a common maximum deterioration date D > d. For this case, we give two pseudopolynomial time algorithms: one runs in O(n²d(D − d) time and O(nd(D − d)) space, the other runs in p_j)²) time and p_j) space. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 511–523, 1998     

Optimal control of a production‐inventory system with both backorders and lost sales

We consider the optimal control of a production inventory‐system with a single product and two customer classes where items are produced one unit at a time. Upon arrival, customer orders can be fulfilled from existing inventory, if there is any, backordered, or rejected. The two classes are differentiated by their backorder and lost sales costs. At each decision epoch, we must determine whether or not to produce an item and if so, whether to use this item to increase inventory or to reduce backlog. At each decision epoch, we must also determine whether or not to satisfy demand from a particular class (should one arise), backorder it, or reject it. In doing so, we must balance inventory holding costs against the costs of backordering and lost sales. We formulate the problem as a Markov decision process and use it to characterize the structure of the optimal policy. We show that the optimal policy can be described by three state‐dependent thresholds: a production base‐stock level and two order‐admission levels, one for each class. The production base‐stock level determines when production takes place and how to allocate items that are produced. This base‐stock level also determines when orders from the class with the lower shortage costs (Class 2) are backordered and not fulfilled from inventory. The order‐admission levels determine when orders should be rejected. We show that the threshold levels are monotonic (either nonincreasing or nondecreasing) in the backorder level of Class 2. We also characterize analytically the sensitivity of these thresholds to the various cost parameters. Using numerical results, we compare the performance of the optimal policy against several heuristics and show that those that do not allow for the possibility of both backordering and rejecting orders can perform poorly.© 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

Yield randomness,cost tradeoffs,and diversification in the EOQ model

Existing production/inventory models with random (variable) yield take the yield distribution as given. This work takes a step towards selecting the optimal yield randomness, jointly with lot sizing decisions. First, we analyze an EOQ model where yield variance and lot size are to be selected simultaneously. Two different cost structures are considered. Secondly, we consider source diversification (‘second sourcing’) as a means of reducing effective yield randomness, and trade its benefits against its costs. Conditions for the superiority of diversification between two sources with distinct yield distributions over a single source are derived. The optimal number of identical sources is also analyzed. Some comments on the congruence of the results with recent JIT practices are provided.     

Optimal reject allowance with constant marginal production efficiency

A job shop must fulfill an order for N good items. Production is conducted in “lots,” and the number of good items in a lot can be accurately determined only after production of that lot is completed. If the number of good items falls short of the outstanding order, the shop must produce further lots, as necessary. Processes with “constant marginal production efficiency” are investigated. The revealed structure allows efficient exact computation of optimal policy. The resulting minimal cost exhibits a consistent (but not universal) pattern whereby higher quality of production is advantageous even at proportionately higher marginal cost.     

Optimal control of an M/G/1 queue with impatient priority customers

An optimal operating policy is characterized for the infinite‐horizon average‐cost case of a single server queueing control problem. The server may be turned on at arrival epochs or off at departure epochs. Two classes of customers, each of them arriving according to an independent Poisson processes, are considered. An arriving 1‐customer enters the system if the server is turned on upon his arrival, or if the server is on and idle. In the former case, the 1‐customer is selected for service ahead of those customers waiting in the system; otherwise he leaves the system immediately. 2‐Customers remain in the system until they complete their service requirements. Under a linear cost structure, this paper shows that a stationary optimal policy exists such that either (1) leaves the server on at all times, or (2) turns the server off when the system is empty. In the latter case, we show that the stationary optimal policy is a threshold strategy, this feature being commonplace in most of priority queueing systems and inventory models. However, the optimal policy in our model is determined by two thresholds instead of one. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 201–209, 2001