Minimizing makespan on a single batch processing machine with nonidentical job sizes

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst‐case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst‐case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 226–240, 2001     

Opportunistic retooling of a flexible machine subject to failure

A set of jobs can be processed without interruption by a flexible machine only if the set of tools required by all jobs can be loaded in the tool magazine. However, in practice the total number of tools required by a job set would exceed the tool magazine capacity. In such situations, the job set has to be carefully partitioned at the start of the production run such that each partition can be processed without interruption. During the production run, if there are unscheduled machine downtimes due to machine failure, this provides an additional opportunity to optimally retool the magazine for a smaller job set consisting of just the unprocessed jobs. In this paper, we study job sequencing rules that allow us to minimize the total expected cost of machine down time due to machine failures and magazine retooling, assuming a dynamic re‐sequencing of the unprocessed jobs after each machine failure. Using these rules, we develop a branch‐and‐bound heuristic that allows us to solve problems of reasonable size. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 79–97, 2001     

Analysis of a new vehicle scheduling and location problem

We consider a container terminal discharging containers from a ship and locating them in the terminal yard. Each container has a number of potential locations in the yard where it can be stored. Containers are moved from the ship to the yard using a fleet of vehicles, each of which can carry one container at a time. The problem is to assign each container to a yard location and dispatch vehicles to the containers so as to minimize the time it takes to download all the containers from the ship. We show that the problem is NP‐hard and develop a heuristic algorithm based on formulating the problem as an assignment problem. The effectiveness of the heuristic is analyzed from both worst‐case and computational points of view. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 363–385, 2001     

The shortest queue model with jockeying

In this article we deal with the shortest queue model with jockeying. We assume that the arrivals are Poisson, each of the exponential servers has his own queue, and jockeying among the queues is permitted. Explicit solutions of the equilibrium probabilities, the expected customers, and the expected waiting time of a customer in the system are given, which only depend on the traffic intensity. Numerical results can be easily obtained from our solutions. Several examples are provided in the article.     

Some two-on-two homogeneous stochastic combats

In this article we consider two versions of two-on-two homogeneous stochastic combat and develop expressions, in each case, for the state probabilities. The models are natural generalizations of the exponential Lanchester square law model. In the first version, a marksman whose target is killed resumes afresh the killing process on a surviving target; in the second version, the marksman whose target is killed merely uses up his remaining time to a kill on a surviving target. Using the state probabilities we then compute such important combat measures as (1) the mean and variance of the number of survivors as they vary with time for each of the sides, (2) the win probabilities for each of the sides, and (3) the mean and variance of the battle duration time. As an application, computations were made for the specific case of a gamma (2) interfiring time random variable for each side and the above combat measures were compared with the appropriate exponential and deterministic Lanchester square law approximations. The latter two are shown to be very poor approximations in this case.     

Learning and costs in airframe production: A multiple-output production function approach

This article examines the influence of both production rate and learning on airframe program costs. A dynamic multiple-output production model is developed and is used to observe the cost impact of changes in production rate and learning. Several simulations are performed to demonstrate the sensitivity of the optimal time path of cost to changes in the model parameters. The model is applied by estimating parameters from the F102 airframe program.     

On nonpreemptive strategies in stochastic scheduling

It is shown that there is an optimal strategy for a class of stochastic scheduling problems which is nonpreemptive. The results which yield this conclusion are generalizations of previous ones due to Glazebrook and Gittins. These new results also lead to an evaluation of the performance of nonpreemptive strategies in a large class of problems of practical interest.     

Inventory models with a mixture of backorders and lost sales

This article presents several single-echelon, single-item, static demand inventory models for situations in which, during the stockout period, a fraction b of the demand is backordered and the remaining fraction 1 - b is lost forever. Both deterministic and stochastic demand are considered. although the case of stochastic demand is treated heuristically. In each situation, a mathematical model representing the average annual cost of operating the inventory system is developed. and an optimum operating policy derived. At the extremes b=1 and b=0 the models presented reduce to the usual backorders and lost sales cases, respectively.     

Johnson's approximate method for the 3 × n job shop problem

The effectiveness of Johnson's Approximate Method (JAM) for the 3 × n job shop scheduling problems was examined on 1,500 test cases with n ranging from 6 to 50 and with the processing times A_i, B_i, C_i (for item i on machines A, B, C) being uniformly and normally distributed. JAM proved to be quite effective for the case B_i ? max (A_i, C_i) and optimal for B_i, ? min (A_i, C_i).