Dynamic routing of prioritized warranty repairs

Recent years have seen a strong trend toward outsourcing warranty repair services to outside vendors. In this article we consider the problem of dynamically routing warranty repairs to service vendors when warranties have priority levels. Each time an item under warranty fails, it is sent to one of the vendors for repair. Items covered by higher priority warranty receive higher priority in repair service. The manufacturer pays a fixed fee per repair and incurs a linear holding cost while an item is undergoing or waiting for repair. The objective is to minimize the manufacturer's long‐run average cost. Because of the complexity of the problem, it is very unlikely that there exist tractable ways to find the optimal routing strategies. Therefore, we propose five heuristic routing procedures that are applicable to real‐life problems. We evaluate the heuristics using simulation. The simulation results show that the index‐based “generalized join the shortest queue” policy, which applies a single policy improvement step to an initial state‐independent policy, performs the best among all five heuristics. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Scheduling economic lot sizes in deteriorating production systems

The paper considers the economic lot scheduling problem (ELSP) where production facility is assumed to deteriorate, owing to aging, with an increasing failure rate. The time to shift from an “in‐control” state to an “out‐of‐control” state is assumed to be normally distributed. The system is scheduled to be inspected at the end of each production lot. If the process is found to be in an “out‐of‐control” state, then corrective maintenance is performed to restore it to an “in‐control” state before the start of the next production run. Otherwise, preventive maintenance is carried out to enhance system reliability. The ELSP is formulated under the capacity constraint taking into account the quality related cost due to possible production of non‐conforming items, process inspection, and maintenance costs. In order to find a feasible production schedule, both the common cycle and time‐varying lot sizes approaches are utilized. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 650–661, 2003     

Strategic capacity decision‐making in a stochastic manufacturing environment using real‐time approximate dynamic programming

In this study, we illustrate a real‐time approximate dynamic programming (RTADP) method for solving multistage capacity decision problems in a stochastic manufacturing environment, by using an exemplary three‐stage manufacturing system with recycle. The system is a moderate size queuing network, which experiences stochastic variations in demand and product yield. The dynamic capacity decision problem is formulated as a Markov decision process (MDP). The proposed RTADP method starts with a set of heuristics and learns a superior quality solution by interacting with the stochastic system via simulation. The curse‐of‐dimensionality associated with DP methods is alleviated by the adoption of several notions including “evolving set of relevant states,” for which the value function table is built and updated, “adaptive action set” for keeping track of attractive action candidates, and “nonparametric k nearest neighbor averager” for value function approximation. The performance of the learned solution is evaluated against (1) an “ideal” solution derived using a mixed integer programming (MIP) formulation, which assumes full knowledge of future realized values of the stochastic variables (2) a myopic heuristic solution, and (3) a sample path based rolling horizon MIP solution. The policy learned through the RTADP method turned out to be superior to polices of 2 and 3. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

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     

Makespan minimization in the two‐machine flowshop batch scheduling problem

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part‐types are to be produced in a flexible manufacturing cell organized into a two‐stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP‐hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 128–144, 2000     

The impact of demand uncertainty on product line design under endogenous substitution

The existing product line design literature devotes little attention to the effect of demand uncertainty. Due to demand uncertainty, the supply‐demand mismatch is inevitable which leads to different degrees of lost sales depending on the configuration of product lines. In this article, we adopt a stylized two‐segment setup with uncertain market sizes and illustrate the interplay between two effects: risk pooling that mitigates the impact of demand uncertainty and market segmentation that facilitates consumer differentiation. Compared to downward substitution, inducing bidirectional substitution through product line decisions including quality levels and prices can yield greater risk pooling effects. However, we show that the additional benefit from the risk pooling effect cannot compensate for the reduced market segmentation effect. We demonstrate that the presence of demand uncertainty can reduce the benefit of market segmentation and therefore the length of product lines in terms of the difference between products. We also propose three heuristics that separate product line and production decisions; each of these heuristics corresponds to one particular form of demand substitution. Our numerical studies indicate that the best of the three heuristics yields performance that is close to optimality. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 143–157, 2015     

Minimax and maximin facility location problems on a sphere

The problem dealt with in this article is as follows. There are n “demand points” on a sphere. Each demand point has a weight which is a positive constant. A facility must be located so that the maximum of the weighted distances (distances are the shortest arcs on the surface of the sphere) is minimized; this is called the minimax problem. Alternatively, in the maximin problem, the minimum weighted distance is maximized. A setup cost associated with each demand point may be added for generality. It is shown that any maximin problem can be reparametrized into a minimax problem. A method for finding local minimax points is described and conditions under which these are global are derived. Finally, an efficient algorithm for finding the global minimax point is constructed.     

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.     

Scheduling multiple products on parallel machines with setup costs

We consider a class of production scheduling models with m identical machines in parallel and k different product types. It takes a time p_i to produce one unit of product type i on any one of the machines. There is a demand stream for product type i consisting of n_i units with each unit having a given due date. Before a machine starts with the production of a batch of products of type i a setup cost c is incurred. We consider several different objective functions. Each one of the objective functions has three components, namely a total setup cost, a total earliness cost, and a total tardiness cost. In our class of problems we find a relatively large number of problems that can be solved either in polynomial time or in pseudo‐polynomial time. The polynomiality or pseudo‐polynomiality is achieved under certain special conditions that may be of practical interest; for example, a regularity pattern in the string of due dates combined with earliness and tardiness costs that are similar for different types of products. The class of models we consider includes as special cases discrete counterparts of a number of inventory models that have been considered in the literature before, e.g., Wagner and Whitin (Manage Sci 5 (1958), 89–96) and Zangwill (Oper Res 14 (1966), 486–507; Manage Sci 15 (1969), 506–527). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Case‐based reasoning and improved adaptive search for project scheduling

Most scheduling problems are notoriously intractable, so the majority of algorithms for them are heuristic in nature. Priority rule‐based methods still constitute the most important class of these heuristics. Of these, in turn, parametrized biased random sampling methods have attracted particular interest, due to the fact that they outperform all other priority rule‐based methods known. Yet, even the “best” such algorithms are unable to relate to the full range of instances of a problem: Usually there will exist instances on which other algorithms do better. We maintain that asking for the one best algorithm for a problem may be asking too much. The recently proposed concept of control schemes, which refers to algorithmic schemes allowing to steer parametrized algorithms, opens up ways to refine existing algorithms in this regard and improve their effectiveness considerably. We extend this approach by integrating heuristics and case‐based reasoning (CBR), an approach that has been successfully used in artificial intelligence applications. Using the resource‐constrained project scheduling problem as a vehicle, we describe how to devise such a CBR system, systematically analyzing the effect of several criteria on algorithmic performance. Extensive computational results validate the efficacy of our approach and reveal a performance similar or close to state‐of‐the‐art heuristics. In addition, the analysis undertaken provides new insight into the behaviour of a wide class of scheduling heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 201–222, 2000     

Production scheduling with history‐dependent setup times

We consider a parallel‐machine scheduling problem with jobs that require setups. The duration of a setup does not depend only on the job just completed but on a number of preceding jobs. These setup times are referred to as history‐dependent. Such a scheduling problem is often encountered in the food processing industry as well as in other process industries. In our model, we consider two types of setup times—a regular setup time and a major setup time that becomes necessary after several “hard‐to‐clean” jobs have been processed on the same machine. We consider multiple objectives, including facility utilization, flexibility, number of major setups, and tardiness. We solve several special cases assuming predetermined job sequences and propose strongly polynomial time algorithms to determine the optimal timing of the major setups for given job sequences. We also extend our analysis to develop pseudopolynomial time algorithms for cases with additional objectives, including the total weighted completion time, the total weighted tardiness, and the weighted number of tardy jobs. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Optimal machine capacity expansions with nested limitations under stochastic demand

This paper studies capacity expansions for a production facility that faces uncertain customer demand for a single product family. The capacity of the facility is modeled in three tiers, as follows. The first tier consists of a set of upper bounds on production that correspond to different resource types (e.g., machine types, categories of manpower, etc.). These upper bounds are augmented in increments of fixed size (e.g., by purchasing machines of standard types). There is a second‐tier resource that constrains the first‐tier bounds (e.g., clean room floor space). The third‐tier resource bounds the availability of the second‐tier resource (e.g., the total floor space enclosed by the building, land, etc.). The second and third‐tier resources are expanded at various times in various amounts. The cost of capacity expansion at each tier has both fixed and proportional elements. The lost sales cost is used as a measure for the level of customer service. The paper presents a polynomial time algorithm (FIFEX) to minimize the total cost by computing optimal expansion times and amounts for all three types of capacity jointly. It accommodates positive lead times for each type. Demand is assumed to be nondecreasing in a “weak” sense. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Scheduling with variable time slot costs

In this article, we study a class of new scheduling models where time slot costs have to be taken into consideration. In such models, processing a job will incur certain cost which is determined by the time slots occupied by the job in a schedule. The models apply when operational costs vary over time. The objective of the scheduling models is to minimize the total time slot costs plus a traditional scheduling performance measure. We consider the following performance measures: total completion time, maximum lateness/tardiness, total weighted number of tardy jobs, and total tardiness. We prove the intractability of the models under general parameters and provide polynomial‐time algorithms for special cases with non‐increasing time slot costs.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Sensitivity analysis on responsive pricing and production under imperfect demand updating

This paper examines three types of sensitivity analysis on a firm's responsive pricing and responsive production strategies under imperfect demand updating. Demand has a multiplicative form where the market size updates according to a bivariate normal model. First, we show that both responsive production and responsive pricing resemble the classical pricing newsvendor with posterior demand uncertainty in terms of the optimal performance and first‐stage decision. Second, we show that the performance of responsive production is sensitive to the first‐stage decision, but responsive pricing is insensitive. This suggests that a “posterior rationale” (ie, using the optimal production decision from the classical pricing newsvendor with expected posterior uncertainty) allows a simple and near‐optimal first‐stage production heuristic for responsive pricing. However, responsive production obtains higher expected profits than responsive pricing under certain conditions. This implies that the firm's ability to calculate the first‐stage decision correctly can help determine which responsive strategy to use. Lastly, we find that the firm's performance is not sensitive to the parameter uncertainty coming from the market size, total uncertainty level and information quality, but is sensitive to uncertainty originating from the procurement cost and price‐elasticity.     

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     

Variables inspection for SPC‐quarantined production

When a control chart signals an out‐of‐control condition for a production process, it may be desirable to “quarantine” all units produced since the last in‐control SPC sample. This paper presents an efficient procedure for variables inspection of such “SPC quarantined” product. A Bayesian sequential inspection procedure is developed which determines whether the out of control production is of acceptable quality. By inspecting the units in reverse of the order in which they were produced, the procedure is also capable of detecting the point at which the process went out of control, thus eliminating the need to inspect units produced prior to the onset of the out of control condition. Numerical examples are presented, and the performance characteristics of the procedure are demonstrated using Monte Carlo simulation. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 159–171, 2001     

Production to order and off‐line inspection when the production process is partially observable

This study combines inspection and lot‐sizing decisions. The issue is whether to INSPECT another unit or PRODUCE a new lot. A unit produced is either conforming or defective. Demand need to be satisfied in full, by conforming units only. The production process may switch from a “good” state to a “bad” state, at constant rate. The proportion of conforming units in the good state is higher than in the bad state. The true state is unobservable and can only be inferred from the quality of units inspected. We thus update, after each inspection, the probability that the unit, next candidate for inspection, was produced while the production process was in the good state. That “good‐state‐probability” is the basis for our decision to INSPECT or PRODUCE. We prove that the optimal policy has a simple form: INSPECT only if the good‐state‐probability exceeds a control limit. We provide a methodology to calculate the optimal lot size and the expected costs associated with INSPECT and PRODUCE. Surprisingly, we find that the control limit, as a function of the demand (and other problem parameters) is not necessarily monotone. Also, counter to intuition, it is possible that the optimal action is PRODUCE, after revealing a conforming unit. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

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.     

Optimization and mediated bartering models for ground delay programs

The Federal Aviation Administration (FAA) and the airline community within the United States have adopted a new paradigm for air traffic flow management, called Collaborative Decision Making (CDM). A principal goal of CDM is shared decision‐making responsibility between the FAA and airlines, so as to increase airline control over decisions that involve economic tradeoffs. So far, CDM has primarily led to enhancements in the implementation of Ground Delay Programs, by changing procedures for allocating slots to airlines and exchanging slots between airlines. In this paper, we discuss how these procedures may be formalized through appropriately defined optimization models. In addition, we describe how inter‐airline slot exchanges may be viewed as a bartering process, in which each “round” of bartering requires the solution of an optimization problem. We compare the resulting optimization problem with the current procedure for exchanging slots and discuss possibilities for increased decision‐making capabilities by the airlines. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Asymptotic distribution of some multivariate “success run” renewal processes,applied to a 2-i.i.d. unit repairable system

If the probability of “failure” in a multivariate renewal process of the “success run” type is very small, then if certain conditions are imposed on the components of the renewals, the joint distribution of their total durations is approximately exponential with all mass along one line. This result is applied to a 2-i.i.d. unit repairable system of the “1 out of 2:G, Cold Standby” type.