Optimal control of noncollaborative servers in two‐stage tandem queueing systems

We consider two‐stage tandem queueing systems with dedicated servers in each station and a flexible server that is trained to serve both stations. We assume no arrivals, exponential service times, and linear holding costs for jobs present in the system. We study the optimal dynamic assignment of servers to jobs assuming a noncollaborative work discipline with idling and preemptions allowed. For larger holding costs in the first station, we show that (i) nonidling policies are optimal and (ii) if the flexible server is not faster than the dedicated servers, the optimal server allocation strategy has a threshold‐type structure. For all other cases, we provide numerical results that support the optimality of threshold‐type policies. Our numerical experiments also indicate that when the flexible server is faster than the dedicated server of the second station, the optimal policy may have counterintuitive properties, which is not the case when a collaborative service discipline is assumed. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 435–446, 2014     

Analysis of decentralized multi‐product pull systems with lost sales

We study a pull‐type, flexible, multi‐product, and multi‐stage production/inventory system with decentralized two‐card kanban control policies. Each stage involves a processor and two buffers with finite target levels. Production stages, arranged in series, can process several product types one at a time. Transportation of semi‐finished parts from one stage to another is performed in fixed lot sizes. The exact analysis is mathematically intractable even for smaller systems. We present a robust approximation algorithm to model two‐card kanban systems with batch transfers under arbitrary complexity. The algorithm uses phase‐type modeling to find effective processing times and busy period analysis to identify delays among product types in resource contention. Our algorithm reduces the effort required for estimating performance measures by a considerable margin and resolves the state–space explosion problem of analytical approaches. Using this analytical tool, we present new findings for a better understanding of some tactical and operational issues. We show that flow of material in small procurement sizes smoothes flow of information within the system, but also necessitates more frequent shipments between stages, raising the risk of late delivery. Balancing the risk of information delays vis‐à‐vis shipment delays is critical for the success of two‐card kanban systems. Although product variety causes time wasted in setup operations, it also facilitates relatively short production cycles enabling processors to switch from one product type to another more rapidly. The latter point is crucial especially in high‐demand environments. Increasing production line size prevents quick response to customer demand, but it may improve system performance if the vendor lead‐time is long or subject to high variation. Finally, variability in transportation and processing times causes the most damage if it arises at stages closer to the customer. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Collaboration in contingent capacities with information asymmetry

We study the optimal contracting problem between two firms collaborating on capacity investment with information asymmetry. Without a contract, system efficiency is lost due to the profit‐margin differentials among the firms, demand uncertainty, and information asymmetry. With information asymmetry, we demonstrate that the optimal capacity level is characterized by a newsvendor formula with an upward‐adjusted capacity investment cost, and no first‐best solution can be achieved. Our analysis shows that system efficiency can always be improved by the optimal contract and the improvement in system efficience is due to two factors. While the optimal contract may bring the system's capacity level closer to the first‐best capacity level, it prevents the higher‐margin firm from overinvesting and aligns the capacity‐investment decisions of the two firms. Our analysis of a special case demonstrates that, under some circumstances, both firms can benefit from the principal having better information about the agent's costs. © 2007 Wiley Periodicals, Inc. Naval Research Logistics 54:, 2007     

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     

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     

An approximate planning model for distributed computing networks

We develop an approximate planning model for a distributed computing network in which a control system oversees the assignment of information flows and tasks to a pool of shared computers, and describe several optimization applications using the model. We assume that the computers are multithreaded, and have differing architectures leading to varying and inconsistent processing rates. The model is based on a discrete‐time, continuous flow model developed by Graves [Oper Res 34 (1986), 522–533] which provides the steady‐state moments of production and work‐in‐queue quantities. We make several extensions to Graves' model to represent distributed computing networks. First, we approximately model control rules that are nonlinear functions of the work‐in‐queue at multiple stations through a linearization approach. Second, we introduce an additional noise term on production and show its use in modeling the discretization of jobs. Third, we model groups of heterogeneous computers as aggregate, “virtual computing cells” that process multiple tasks simultaneously, using a judiciously selected control rule. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

On‐line algorithms for minimizing makespan on batch processing machines

We consider problem of scheduling jobs on‐line on batch processing machines with dynamic job arrivals to minimize makespan. A batch machine can handle up to B jobs simultaneously. The jobs that are processed together from a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. Each job becomes available at its arrival time, which is unknown in advance, and its processing time becomes known upon its arrival. In the first part of this paper, we address the single batch processing machine scheduling problem. First we deal with two variants: the unbounded model where B is sufficiently large and the bounded model where jobs have two distinct arrival times. For both variants, we provide on‐line algorithms with worst‐case ratio (the inverse of the Golden ratio) and prove that these results are the best possible. Furthermore, we generalize our algorithms to the general case and show a worst‐case ratio of 2. We then consider the unbounded case for parallel batch processing machine scheduling. Lower bound are given, and two on‐line algorithms are presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 241–258, 2001     

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     

A general model of heterogeneous system lifetimes and conditions for system burn‐in

Burn‐in is a technique to enhance reliability by eliminating weak items from a population of items having heterogeneous lifetimes. System burn‐in can improve system reliability, but the conditions for system burn‐in to be performed after component burn‐in remain a little understood mathematical challenge. To derive such conditions, we first introduce a general model of heterogeneous system lifetimes, in which the component burn‐in information and assembly problems are related to the prediction of system burn‐in. Many existing system burn‐in models become special cases and two important results are identified. First, heterogeneous system lifetimes can be understood naturally as a consequence of heterogeneous component lifetimes and heterogeneous assembly quality. Second, system burn‐in is effective if assembly quality variation in the components and connections which are arranged in series is greater than a threshold, where the threshold depends on the system structure and component failure rates. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 364–380, 2003.     

Integrated production scheduling and preventive maintenance planning for a single machine under a cumulative damage failure process

This paper finds the optimal integrated production schedule and preventive maintenance plan for a single machine exposed under a cumulative damage process, and investigates how the optimal preventive maintenance plan interacts with the optimal production schedule. The goal is to minimize the total tardiness. The optimal policy possesses the following properties: Under arbitrary maintenance plan when jobs have common processing time, and different due dates, the optimal production schedule is to order the jobs by earliest due date first rule; and when jobs have common due date and different processing times, the optimal production schedule is shortest processing time first. The optimal maintenance plan is of control limit type under any arbitrary production schedule when machine is exposed under a cumulative damage failure process. Numerical studies on the optimal maintenance control limit of the maintenance plan indicate that as the number of jobs to be scheduled increases, the effect of jobs due dates on the optimal maintenance control limit diminishes. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

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     

Determining a threshold control policy for an imperfect production system with rework jobs

Consider a threshold control policy for an imperfect production system with only a work center handling both regular and rework jobs. An imperfect production system studied here, generates defect jobs by factors other than machine failures. A threshold control or (ω, s) policy sets the guideline for a work center to switch between regular and rework jobs. A production cycle begins with loading and processing of several batches of regular jobs with a lot size equal to s. The outcome of each completed regular job is an independent Bernoulli trial with three possibilities: good, rework, or scrap. Once the work center accumulates more than a threshold ω of rework jobs, it finishes the last batch of regular jobs and switches to rework jobs. The objective of this research is to find a threshold ω and a lot size s that maximize the average long‐term profit. The ultimate goal is to construct a simple algorithm to search for ω and s that can be implemented directly in production management systems, as a result of this work. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 273–301, 1999     

A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times

We investigate a single‐machine scheduling problem for which both the job processing times and due windows are decision variables to be determined by the decision maker. The job processing times are controllable as a linear or convex function of the amount of a common continuously divisible resource allocated to the jobs, where the resource allocated to the jobs can be used in discrete or continuous quantities. We use the common flow allowances due window assignment method to assign due windows to the jobs. We consider two performance criteria: (i) the total weighted number of early and tardy jobs plus the weighted due window assignment cost, and (ii) the resource consumption cost. For each resource consumption function, the objective is to minimize the first criterion, while keeping the value of the second criterion no greater than a given limit. We analyze the computational complexity, devise pseudo‐polynomial dynamic programming solution algorithms, and provide fully polynomial‐time approximation schemes and an enhanced volume algorithm to find high‐quality solutions quickly for the considered problems. We conduct extensive numerical studies to assess the performance of the algorithms. The computational results show that the proposed algorithms are very efficient in finding optimal or near‐optimal solutions. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 41–63, 2017     

Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine

This paper tackles the general single machine scheduling problem, where jobs have different release and due dates and the objective is to minimize the weighted number of late jobs. The notion of master sequence is first introduced, i.e., a sequence that contains at least an optimal sequence of jobs on time. This master sequence is used to derive an original mixed‐integer linear programming formulation. By relaxing some constraints, a Lagrangean relaxation algorithm is designed which gives both lower and upper bounds. The special case where jobs have equal weights is analyzed. Computational results are presented and, although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 50: 2003     

A dual criteria sequencing problem with earliness and tardiness penalties

We consider the problem of sequencing n jobs on a single machine, with each job having a processing time and a common due date. The common due date is assumed to be so large that all jobs can complete by the due date. It is known that there is an O(n log n)‐time algorithm for finding a schedule with minimum total earliness and tardiness. In this article, we consider finding a schedule with dual criteria. The primary goal is to minimize the total earliness and tardiness. The secondary goals are to minimize: (1) the maximum earliness and tardiness; (2) the sum of the maximum of the squares of earliness and tardiness; (3) the sum of the squares of earliness and tardiness. For the first two criteria, we show that the problems are NP‐hard and we give a fully polynomial time approximation scheme for both of them. For the last two criteria, we show that the ratio of the worst schedule versus the best schedule is no more than . © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 422–431, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10020     

Due‐window assignment with unit processing‐time jobs

In due‐window assignment problems, jobs completed within a designated time interval are regarded as being on time, whereas early and tardy jobs are penalized. The objective is to determine the location and size of the due‐window, as well as the job schedule. We address a common due‐window assignment problem on parallel identical machines with unit processing time jobs. We show that the number of candidate values for the optimal due‐window starting time and for the optimal due‐window completion time are bounded by 2. We also prove that the starting time of the first job on each of the machines is either 0 or 1, thus introducing a fairly simple, constant‐time solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A queuing model for due date control in a multiserver repair shop

This paper deals with a repair shop with multiple parallel servers, which has to carry out planned overhauls. Each overhaul consists of a large number of maintenance jobs. The overhaul process is interrupted by randomly arriving emergency jobs. To control the delivery performance of the overhauls, knowledge about the overhaul makespan distribution should be available. Using a 2‐dimensional Markov model, we derive the first and second moment of the overhaul makespan analytically for the case that the repair times of all overhaul jobs are identically and exponentially distributed. For the case of nonidentical repair time distributions, an approximation is presented. Simulation shows that the makespan distribution fitted on these moments gives an excellent approximation. © John Wiley & Sons, Inc. Naval Research Logistics 48: 281–282, 2001     

Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

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.     

Two‐agent scheduling on a single sequential and compatible batching machine

We study two‐agent scheduling on a single sequential and compatible batching machine in which jobs in each batch are processed sequentially and compatibility means that jobs of distinct agents can be processed in a common batch. A fixed setup time is required before each batch is started. Each agent seeks to optimize some scheduling criterion that depends on the completion times of its own jobs only. We consider several scheduling problems arising from different combinations of some regular scheduling criteria, including the maximum cost (embracing lateness and makespan as its special cases), the total completion time, and the (weighted) number of tardy jobs. Our goal is to find an optimal schedule that minimizes the objective value of one agent, subject to an upper bound on the objective value of the other agent. For each problem under consideration, we provide either a polynomial‐time or a pseudo‐polynomial‐time algorithm to solve it. We also devise a fully polynomial‐time approximation scheme when both agents’ scheduling criteria are the weighted number of tardy jobs.