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     

A genetic algorithm methodology for complex scheduling problems

This paper considers the scheduling problem to minimize total tardiness given multiple machines, ready times, sequence dependent setups, machine downtime and scarce tools. We develop a genetic algorithm based on random keys representation, elitist reproduction, Bernoulli crossover and immigration type mutation. Convergence of the algorithm is proved. We present computational results on data sets from the auto industry. To demonstrate robustness of the approach, problems from the literature of different structure are solved by essentially the same algorithm. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 199–211, 1999     

Interchange fees for bank ATM networks

Banks have found it advantageous to connect their Automated Teller Machines (ATMs) in networks so that customers of one bank may use the ATMs of any bank in the network. When this occurs, an interchange fee is paid by the customer's bank to the one that owns the ATM. These have been set by historic interbank negotiation. The paper investigates how a model based on n-player game theory concepts of Shapley value and nucleolus could be used as an alternative way of setting such fees. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 407–417, 1998     

A robust regression technique using compound estimation

Least squares fitting of regression models is a widely used technique. The presence of outliers in the data can have an adverse effect on the method of least squares, resulting in a model that does not adequately fit to the bulk of the data. For this situation, robust regression techniques have been proposed as an improvement to the method of least squares. We propose a robust regression procedure that performs well relative to the current robust methods against a variety of dataset types. Evaluations are performed using datasets without outliers (testing efficiency), with a large percentage of outliers (testing breakdown), and with high leverage outliers (testing bounded influence). The datasets are based on 2-level factorial designs that include axial points to evaluate leverage effects. A Monte Carlo simulation approach is used to evaluate the estimating capability of the proposed procedure relative to several competing methods. We also provide an application to estimating costs for government satellites. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 125–139, 1998     

Meeting seasonal demand for products with limited shelf lives

This article addresses a common misconception concerning production lead time and the use of inventory to meet seasonal demand for products with limited shelf lives. Two fundamental questions are answered: 1) Under what conditions will an increase in product life lead to increased ability to meet demand? 2) Under what conditions will increased levels of starting inventory be beneficial? The results of this analysis assisted a plastics manufacturing firm in making product pricing and inventory decisions. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44 : 473–483, 1997     

Scheduling to minimize release-time resource consumption and tardiness penalties

We consider the problem of scheduling a set of jobs with a common due-date on a single-machine where the release time of a job is related to the amount of resource consumed. The objective is to minimize the total resource consumption and the total tardiness. While the problem is strongly NP-hard in general, we discuss two different special cases for which special properties are identified and used to develop efficient pseudo-polynomial time algorithms. © 1995 John Wiley & Sons, Inc.     

An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines

We consider the multitasking scheduling problem on unrelated parallel machines to minimize the total weighted completion time. In this problem, each machine processes a set of jobs, while the processing of a selected job on a machine may be interrupted by other available jobs scheduled on the same machine but unfinished. To solve this problem, we propose an exact branch‐and‐price algorithm, where the master problem at each search node is solved by a novel column generation scheme, called in‐out column generation, to maintain the stability of the dual variables. We use a greedy heuristic to obtain a set of initial columns to start the in‐out column generation, and a hybrid strategy combining a genetic algorithm and an exact dynamic programming algorithm to solve the pricing subproblems approximately and exactly, respectively. Using randomly generated data, we conduct numerical studies to evaluate the performance of the proposed solution approach. We also examine the effects of multitasking on the scheduling outcomes, with which the decision maker can justify making investments to adopt or avoid multitasking.     

Continuous-time markov duels: Theory and application

This article extends the previous research on Markov duels (stochastic duels between weapons with Markov-dependent fire) to situations in which the time between rounds fired by each duelist is a continuous random variable that depends on the state of combat. Three starting conditions for the duels are considered: simultaneous detection, surprise by one duelist with continuous time detection by his opponent, and surprise with discrete time detection. The amount of surprise is treated as both a constant and a random variable. An application of these models to an evaluation of armored vehicles is described. The methods used to consider a variety of engagement ranges, tactical situations, and target types (both lethal and nonlethal) are discussed. The procedure for incorporating nonduel attrition into the analysis is described and the exchange rate (the expected number of enemy targets killed per armored vehicle killed) is derived.     

Stochastic production capacity: A bane or a boon for quick response supply chains?

The quick response (QR) system that can cope with demand volatility by shortening lead time has been well studied in the literature. Much of the existing literature assumes implicitly or explicitly that the manufacturers under QR can always meet the demand because the production capacity is always sufficient. However, when the order comes with a short lead time under QR, availability of the manufacturer's production capacity is not guaranteed. This motivates us to explore QR in supply chains with stochastic production capacity. Specifically, we study QR in a two-echelon supply chain with Bayesian demand information updating. We consider the situation where the manufacturer's production capacity under QR is uncertain. We first explore how stochastic production capacity affects supply chain decisions and QR implementation. We then incorporate the manufacturer's ability to expand capacity into the model. We explore how the manufacturer determines the optimal capacity expansion decision, and the value of such an ability to the supply chain and its agents. Finally, we extend the model to the two-stage two-ordering case and derive the optimal ordering policy by dynamic programming. We compare the single-ordering and two-ordering cases to generate additional managerial insights about how ordering flexibility affects QR when production capacity is stochastic. We also explore the transparent supply chain and find that our main results still hold.     

Purchase and retrieval competition for seasonal produce

We study the competition problem of purchase and multiretrieval of perishable seasonal produce, where wholesalers purchase and stock their products in the first period, and then retrieve and sell them in subsequent periods. We first consider the duopoly case and assume that the prices are exogenous and fluctuate. In each period, after the price realization, the wholesalers retrieve some stock from their warehouses to satisfy their demands. One wholesaler's unsatisfied customers can switch to another and be satisfied by its left retrieved products. Any unsold retrieved stock has no salvage value and any unsatisfied demand is lost. The unretrieved stock is carried to the next period at a perishable rate. The wholesalers compete for the substitute demand by determining their own purchase and retrieval quantities. We show the existence and uniqueness of a pure-strategy Nash equilibrium, and that the Nash equilibrium strategy has the simple “sell-down-to” structure. We also consider the general N-person game and show the existence of the Nash equilibrium, and characterize the structure of the equilibrium strategy for the symmetric case. In addition, we consider the case with endogenous prices, and show that the problem reduces to a repeated newsvendor game with price and inventory competition. We derive the conditions under which a unique Nash equilibrium exists and characterize the equilibrium strategy. Finally, we conduct numerical studies to examine the impacts of the model parameters on the equilibrium outcomes and to generate managerial insights.