The open shop scheduling problem with a given sequence of jobs on one machine

The paper considers the open shop scheduling problem to minimize the make-span, provided that one of the machines has to process the jobs according to a given sequence. We show that in the preemptive case the problem is polynomially solvable for an arbitrary number of machines. If preemption is not allowed, the problem is NP-hard in the strong sense if the number of machines is variable, and is NP-hard in the ordinary sense in the case of two machines. For the latter case we give a heuristic algorithm that runs in linear time and produces a schedule with the makespan that is at most 5/4 times the optimal value. We also show that the two-machine problem in the nonpreemptive case is solvable in pseudopolynomial time by a dynamic programming algorithm, and that the algorithm can be converted into a fully polynomial approximation scheme. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 705–731, 1998     

Inventory management under random supply disruptions and partial backorders

We explore the management of inventory for stochastic-demand systems, where the product's supply is randomly disrupted for periods of random duration, and demands that arrive when the inventory system is temporarily out of stock become a mix of backorders and lost sales. The stock is managed according to the following modified (s, S) policy: If the inventory level is at or below s and the supply is available, place an order to bring the inventory level up to S. Our analysis yields the optimal values of the policy parameters, and provides insight into the optimal inventory strategy when there are changes in the severity of supply disruptions or in the behavior of unfilled demands. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 687–703, 1998     

Minimizing weighted mean absolute deviation of flow times in single machine systems

We discuss the problem of scheduling several jobs on a single machine with the objective of minimizing the weighted mean absolute deviation of flow times around the weighted mean flow time. We first show that the optimal schedule is W-shaped. For the unweighted case, we show that all optimal schedules are V-shaped. This characterization enables us to show that the problem is NP-hard. We then provide a pseudopolynomial algorithm for the unweighted problem. Finally, we consider three heuristic algorithms for the unweighted problem and report computational experience with these algorithms. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 297–311, 1998     

Optimal shift scheduling: A branch‐and‐price approach

We present a branch‐and‐price technique for optimal staff scheduling with multiple rest breaks, meal break, and break windows. We devise and implement specialized branching rules suitable for solving the set covering type formulation implicitly, using column generation. Our methodology is more widely applicable and computationally superior to the alternative methods in the literature. We tested our methodology on 365 test problems involving between 1728 and 86400 shift variations, and 20 demand patterns. In a direct comparison with an alternative method, our approach yields significant improvements both in cpu time and in the number of problem instances solved to optimality. The improvements were particularly marked for problems involving larger numbers of feasible shifts. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 185–200, 2000     

Minimizing quality control costs for laboratory instruments using information delays

This paper proposes the use of a cost-based statistical process control system for monitoring the quality of an unreliable analytical machine. In this environment the accuracy of the process cannot be determined by inspecting the output, but must be verified by analyzing standards of known values. The results demonstrate that a significant cost savings can be obtained if analytical results are placed in a “buffer” and their release delayed until the accuracy of the test can be assured. Results suggest the approach not only dramatically improves the quality of results reported but also significantly reduces the expected total cost of testing. © 1996 John Wiley & Sons, Inc.     

Reliability models and inference for systems operating in different environments

We consider a class of models for the reliability function of a series system. The models incorporate dependence of the function on environmental covariates. On the basis of censored data obtained by monitoring several series systems operating under various sets of values of the covariates, estimators are derived of the reliability function of a series system operating under a different set of values of the covariates. Estimators of various functionals of the reliability function, such as the trimmed mean and quantiles, are also presented. Asymptotic properties of the estimators are obtained with the use of the framework of counting processes and martingales. The loss in efficiency in estimating the regression parameters and the reliability function is also examined when one assumes a more general semiparametric model, when in fact the true model belongs to a more restricted model. We illustrate these procedures with the use of accelerated failure-time data. © 1996 John Wiley & Sons, Inc.     

The single period procurement problem where dedicated supplier capacity can be reserved

In this article we consider the single period procurement strategy for an item with uncertainty in its demand and uncertainty in the capacity of the supplier. Dedicated capacity can be ensured by paying a premium charge to the supplier. The other decision variable is the replenishment quantity to request. It turns out to be very easy to select the best value of this latter quantity. On the other hand, we are only able to characterize the general behavior of the expected profit as a function of the level of dedicated capacity. In general, there can be multiple local maxima as a function of the dedicated capacity. However, for the special, but important, case of normally distributed demand, normally distributed capacity and a linear cost for reserving capacity, an algorithm is developed for finding the best level of dedicated capacity. Some preliminary insights regarding the extension to multiple periods are presented. © 1995 John Wiley & Sons, Inc.     

A generalized model for the economic design of x̄control charts for production systems with increasing failure rate and early replacement

This article generalizes the model for the economic design of x̄-control charts of Duncan [4], starting from the more recent papers of Lorenzen and Vance [8] and Banerjee and Rahim [3]. The classical model of Duncan [4] and its several extensions including the unified model of Lorenzen and Vance [8] assumed exponentially distributed in-control periods and provided uniform sampling schemes. Banerjee and Rahim [3], however, assumed a Weibull-distributed in-control period having an increasing failure rate and used variable sampling intervals. The present article is an extension of the work of Banerjee and Rahim [3], where a general distribution of in-control periods having an increasing failure rate is assumed and the possibility of age-dependent repair before failure is considered. Several different truncated and nontruncated probability models are chosen. It is proposed that economic benefits can be achieved by adopting a nonuniform inspection scheme and by truncating a production cycle when it attains a certain age. Numerical examples are presented to support this proposition. Finally, the effect of model specification in the choice of failure mechanism is investigated. © 1993 John Wiley & Sons, Inc.     

A linear relaxation heuristic for the generalized assignment problem

We examine the basis structure of the linear relaxation of the generalized assignment problem. The basis gives a surprising amount of information. This leads to a very simple heuristic that uses only generalized network optimization codes. Lower bounds can be generated by cut generation, where the violated inequalities are found directly from the relaxation basis. An improvement heuristic with the same flavor is also presented.