Cyclical schedules for the joint replenishment problem with dynamic demands

The Joint Replenishment Problem (JRP) involves production planning for a family of items. The items have a coordinated cost structure whereby a major setup cost is incurred whenever any item in the family is produced, and an item-specific minor setup cost is incurred whenever that item is produced. This paper investigates the performance of two types of cyclical production schedules for the JRP with dynamic demands over a finite planning horizon. The cyclical schedules considered are: (1) general cyclical schedules—schedules where the number of periods between successive production runs for any item is constant over the planning horizon—and (2) power-of-two schedules—a subset of cyclical schedules for which the number of periods between successive setups must be a power of 2. The paper evaluates the additional cost incurred by requiring schedules to be cyclical, and identifies problem characteristics that have a significant effect on this additional cost. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 577–589, 1997.     

Multiproduct batching and scheduling with buffered rework: The case of a car paint shop

We study a problem of scheduling products on the same facility, which is motivated by a car paint shop. Items of the same product are identical. Operations on the items are performed sequentially in batches, where each batch is a set of operations on the same product. Some of the produced items are of the required good quality and some items can be defective. Defectiveness of an item is determined by a given simulated function of its product, its preceding product, and the position of its operation in the batch. Defective items are kept in a buffer of a limited capacity, and they are then remanufactured at the same facility. A minimum waiting time exists for any defective item before its remanufacturing can commence. Each product has a sequence independent setup time which precedes its first operation or its operation following an operation of another product. A due date is given for each product such that all items of the same product have the same due date and the objective is to find a schedule which minimizes maximum lateness of product completion times with respect to their due dates. The problem is proved NP‐hard in the strong sense, and a heuristic Group Technology (GT) solution approach is suggested and analyzed. The results justify application of the GT approach to scheduling real car paint shops with buffered rework. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 458–471, 2014     

When is a base stock policy optimal in recovering disrupted cyclic schedules?

The extended economic lot scheduling problem (EELSP) is concerned with scheduling the production of a set of items in a single facility to minimize the long-run average holding, backlogging, and setup costs. Given an efficient cyclic production schedule for the EELSP, called the target schedule, we consider the problem of how to schedule production after a single schedule disruption. We propose a base stock policy, characterized by a base stock vector, that prescribes producing an item until its inventory level reaches the peak inventory of the target schedule corresponding to the item's position in the production sequence. We show that the base stock policy is always successful in recovering the target schedule. Moreover, the base stock policy recovers the target schedule at minimal excess over average cost whenever the backorder costs are proportional to the processing times. This condition holds, for example, when the value of the items is proportional to their processing times, and a common inventory carrying cost and a common service level is used for all the items. Alternatively, the proportionality condition holds if the inventory manager is willing to select the service levels from a certain set that is large enough to guarantee any minimal level of service, and then uses the imputed values for the backorder costs. When the proportionality condition holds we provide a closed-form expression for the total relevant excess over average cost of recovering the target schedule. We assess the performance of the base stock policy when the proportionality condition does not hold through a numerical study, and suggest some heuristic uses of the base stock policy. © 1994 John Wiley & Sons, Inc.     

Strategic investment to reduce setup times in the economic lot scheduling problem

This article considers the Economic Lot Scheduling Problem where setup times and costs can be reduced by an initial investment that is amortized over time. The objective is to determine a multiple-item single facility cyclic schedule to minimize the long run average holding and setup costs plus the amortized investment. We develop a lower bound on the long run average inventory carrying and setup costs as a function of the setup times, and show that this lower bound is increasing concave on the setup times when the out-of-pocket setup costs are zero or proportional to the setup times. We then develop a model that may be helpful in deciding the magnitude and the distribution of a one-time investment in reducing the setup times when the investment is amortized over time. Numerical results based on randomly generated problems, and on Bomberger's ten item problem indicate that significant overall savings are possible for highly utilized facilities. Most of the savings are due to a significant reduction in the long run average holding cost. © 1995 John Wiley & Sons, Inc.     

Three ways of obtaining the average cost expression in a problem related to joint replenishment inventory control

This paper does not present a new result, rather it is meant to illustrate the choice of modelling procedures available to an analyst in a typical inventory control problem. The same “average cost per unit time” expression is developed by three quite different procedures. This variety of approaches, as well as the recounting of the author's chronological efforts to solve the problem, should be of interest to the reader. The specific inventory problem studied is one where the controller of an item is faced with random opportunities for replenishment at a reduced setup cost; the problem is an integral component of the broader problem of inventory control of a group of items whose replenishments are coordinated to reduce the costs of production, procurement, and/or transportation.     

A robust policy for serial agile production systems

One of the major problems in modeling production systems is how to treat the job arrival process. Restrictive assumptions such as Markovian arrivals do not represent real world systems, especially if the arrival process is generated by job departures from upstream workstations. Under these circumstances, cost‐effective policies that are robust with respect to the nature of the arrival process become of interest. In this paper, we focus on minimizing the expected total holding and setup costs in a two‐stage produce‐to‐order production system operated by a cross‐trained worker. We will show that if setup times are insignificant in comparison with processing times, then near‐optimal policies can be generated with very robust performances with respect to the arrival process. We also present conditions under which these near‐optimal policies can be obtained by using only the arrival and service rates. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Customer delays in M/M/c repair systems with spares

A service center to which customers bring failed items for repair is considered. The items are exchangeable in the sense that a customer is ready to take in return for the failed item he brought to the center any good item of the same kind. This exchangeability feature makes it possible for the service center to possess spares. The focus of the article is on customer delay in the system—the time that elapses since the arrival of a customer with a failed item and his departure with a good one—when repaired items are given to waiting customers on a FIFO basis. An algorithm is developed for the computation of the delay distribution when the item repair system operates as an M/M/c queue.     

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     

Multi‐item capacitated lot‐sizing problems with setup times and pricing decisions

We study a multi‐item capacitated lot‐sizing problem with setup times and pricing (CLSTP) over a finite and discrete planning horizon. In this class of problems, the demand for each independent item in each time period is affected by pricing decisions. The corresponding demands are then satisfied through production in a single capacitated facility or from inventory, and the goal is to set prices and determine a production plan that maximizes total profit. In contrast with many traditional lot‐sizing problems with fixed demands, we cannot, without loss of generality, restrict ourselves to instances without initial inventories, which greatly complicates the analysis of the CLSTP. We develop two alternative Dantzig–Wolfe decomposition formulations of the problem, and propose to solve their relaxations using column generation and the overall problem using branch‐and‐price. The associated pricing problem is studied under both dynamic and static pricing strategies. Through a computational study, we analyze both the efficacy of our algorithms and the benefits of allowing item prices to vary over time. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Analysis of the finite‐source multiclass priority queue with an unreliable server and setup time

In this article, we study a queueing system serving multiple classes of customers. Each class has a finite‐calling population. The customers are served according to the preemptive‐resume priority policy. We assume general distributions for the service times. For each priority class, we derive the steady‐state system size distributions at departure/arrival and arbitrary time epochs. We introduce the residual augmented process completion times conditioned on the number of customers in the system to obtain the system time distribution. We then extend the model by assuming that the server is subject to operation‐independent failures upon which a repair process with random duration starts immediately. We also demonstrate how setup times, which may be required before resuming interrupted service or picking up a new customer, can be incorporated in the model. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A modified block replacement policy

A well known preventive replacement policy is the block replacement policy (BRP). In such a policy the item undergoes a planned replacement at a sequence of equally spaced time points independent of failure history. The main advantage of a BRP is its simplicity, because under this policy it is unnecessary to keep detailed records about times of failures or ages of items. The main drawback of a BRP is that at planned replacement times we may be replacing practically new items. In this paper we study a modified BRP which is free of this drawback. We calculate the expected cost of following a modified BRP for lifetime distributions possessing a special structure and illustrate it for the case of an Erlang distribution. A numerical comparison is made between a modified BRP and a standard BRP for the special case of a two stage Erlang distribution.     

Flow‐shop batch scheduling with identical processing‐time jobs

In many practical situations of production scheduling, it is either necessary or recommended to group a large number of jobs into a relatively small number of batches. A decision needs to be made regarding both the batching (i.e., determining the number and the size of the batches) and the sequencing (of batches and of jobs within batches). A setup cost is incurred whenever a batch begins processing on a given machine. This paper focuses on batch scheduling of identical processing‐time jobs, and machine‐ and sequence‐independent setup times on an m‐machine flow‐shop. The objective is to find an allocation to batches and their schedule in order to minimize flow‐time. We introduce a surprising and nonintuitive solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Multiple subset sum with inclusive assignment set restrictions

In a traditional multiple subset sum problem (MSSP), there is a given set of items and a given set of bins (or knapsacks) with identical capacities. The objective is to select a subset of the items and pack them into the bins such that the total weight of the selected items is maximized. However, in many applications of the MSSP, the bins have assignment restrictions. In this article, we study the subset sum problem with inclusive assignment set restrictions, in which the assignment set of one item (i.e., the set of bins that the item may be assigned to) must be either a subset or a superset of the assignment set of another item. We develop an efficient 0.6492‐approximation algorithm and test its effectiveness via computational experiments. We also develop a polynomial time approximation scheme for this problem. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Performance evaluation of a production/inventory system with periodic review and endogenous lead times

This paper considers a discrete time, single item production/inventory system with random period demands. Inventory levels are reviewed periodically and managed using a base‐stock policy. Replenishment orders are placed with the production system which is capacitated in the sense that there is a single server that sequentially processes the items one at a time with stochastic unit processing times. In this setting the variability in demand determines the arrival pattern of production orders at the queue, influencing supply lead times. In addition, the inventory behavior is impacted by the correlation between demand and lead times: a large demand size corresponds to a long lead time, depleting the inventory longer. The contribution of this paper is threefold. First, we present an exact procedure based on matrix‐analytic techniques for computing the replenishment lead time distribution given an arbitrary discrete demand distribution. Second, we numerically characterize the distribution of inventory levels, and various other performance measures such as fill rate, base‐stock levels and optimal safety stocks, taking the correlation between demand and lead times into account. Third, we develop an algorithm to fit the first two moments of the demand and service time distribution to a discrete phase‐type distribution with a minimal number of phases. This provides a practical tool to analyze the effect of demand variability, as measured by its coefficient of variation, on system performance. We also show that our model is more appropriate than some existing models of capacitated systems in discrete time. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A simple approximation for a multistage capacitated production-inventory system

We develop a simple approximation for multistage production-inventory systems with limited production capacity and variable demands. Each production stage follows a base-stock policy for echelon inventory, constrained by production capacity and the availability of upstream inventory. Our objective is to find base-stock levels that approximately minimize holding and backorder costs. The key step in our procedure approximates the distribution of echelon inventory by a sum of exponentials; the parameters of the exponentials are chosen to match asymptotically exact expressions. The computational requirements of the method are minimal. In a test bed of 72 problems, each with five production stages, the average relative error for our approximate optimization procedure is 1.9%. © 1996 John Wiley & Sons, Inc.     

Optimal job splitting on a multi‐slot machine with applications in the printing industry

In this article, we define a scheduling/packing problem called the Job Splitting Problem, motivated by the practices in the printing industry. There are n types of items to be produced on an m‐slot machine. A particular assignment of the types to the slots is called a “run” configuration and requires a setup cost. Once a run begins, the production continues according to that configuration and the “length” of the run represents the quantity produced in each slot during that run. For each unit of production in excess of demand, there is a waste cost. Our goal is to construct a production plan, i.e., a set of runs, such that the total setup and waste cost is minimized. We show that the problem is strongly NP‐hard and propose two integer programming formulations, several preprocessing steps, and two heuristics. We also provide a worst‐case bound for one of the heuristics. Extensive tests on real‐world and randomly generated instances show that the heuristics are both fast and effective, finding near‐optimal solutions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Queueing models for spares provisioning

A population of items which break down at random times and require repair is studied (the classic “machine repair problem with spares”). It is desired to determine the number of repair channels and spares required over a multiyear planning horizon in which population size and component reliability varies, and a service level constraint is imposed. When an item fails, a spare (if available) is immediately dispatched to replace the failed item. The failed item is removed, transported to the repair depot, repaired, and then placed in the spares pool (which is constrained to be empty not more than 10% of the time) unless there is a backlog of requests for spares, in which case it is dispatched immediately. The first model considered treats removal, transportation, and repair as one service operation. The second model is a series queue which allows for the separate treatment of removal, transportation, and repair. Breakdowns are assumed Poisson and repair times exponential.     

A dynamic-programming approach to continuous-review obsolescent inventory problems

Inventory models of modern production and service operations should take into consideration possible exogenous failures or the abrupt decline of demand resulting from obsolescence. This article analyzes continuous-review versions of the classical obsolescence problem in inventory theory. We assume a deterministic demand model and general continuous random times to obsolescence (“failure”). Using continuous dynamic programming, we investigate structural properties of the problem and propose explicit and workable solution techniques. These techniques apply to two fairly wide (and sometimes overlapping) classes of failure distributions: those which are increasing in failure rate and those which have finite support. Consequently, several specific failure processes in continuous time are given exact solutions. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 757–774, 1997     

Simultaneous optimization of efficiency and performance balance measures in single-machine scheduling problems

Manufacturing and service organizations routinely face the challenge of scheduling jobs, orders, or individual customers in a schedule that optimizes either (i) an aggregate efficiency measure, (ii) a measure of performance balance, or (iii) some combination of these two objectives. We address these questions for single-machine job scheduling systems with fixed or controllable due dates. We show that a large class of such problems can be optimized by solving either a single instance or a finite sequence of instances of the so-called (SQC) problem, in which the sum of general quasiconvex functions of the jobs' completion times is to be minimized. To solve a single instance of (SQC), we develop an efficient, though pseudopolynomial algorithm, based on dynamic programming. The algorithm generates a solution that is optimal among all schedules whose starting time is restricted to the points of a prespecified (arbitrary) grid. The algorithm is embedded in an iterative procedure, where in each iteration a specific instance of (SQC) is solved. Special attention is given to the simultaneous minimization of the mean and variance of completion times. © 1993 John Wiley & Sons, Inc.     

Optimal design of a multi-item,multi-location,multi-repair type repair and supply system

The design of a system with many locations, each with many items which may fail while in use, is considered. When items fail, they require repair; the particular type of repair being governed by a probability distribution. As repairs may be lengthy, spares are kept on hand to replace failed items. System ineffectiveness is measured by expected weighted shortages over all items and locations, in steady state. This can be reduced by either having more spares or shorter expected repair times. Design consists of a provisioning of the number of spares for each item, by location; and specifying the expected repair times for each type of repair, by item and location. The optimal design minimizes expected shortages within a budget constraint, which covers both (i) procurement of spares and (ii) procurement of equipment and manning levels for the repair facilities. All costs are assumed to be separable so that a Lagrangian approach is fruitful, yielding an implementable algorithm with outputs useful for sensitivity analysis. A numerical example is presented.