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     

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     

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.     

Waiting times for M/G/1 queues with service-time or delay-dependent server vacations

This article shows how to determine the stationary distribution of the virtual wait in M/G/1 queues with either one-at-a-time or exhaustive server vacations, depending on either service times or accrued workload. For the first type of dependence, each vacation time is a function of the immediately preceding service time or of whether the server finds the system empty after returning from vacation. In this way, it is possible to model situations such as long service times followed by short vacations, and vice versa. For the second type of dependence, the vacation time assigned to an arrival to follow its service is a function of the level of virtual wait reached. By this device, we can model situations in which vacations may be shortened whenever virtual delays have gotten excessive. The method of analysis employs level-crossing theory, and examples are given for various cases of service and vacation-time distributions. A closing discussion relates the new model class to standard M/G/1 queues where the service time is a sum of variables having complex dependencies. © 1992 John Wiley & Sons, Inc.     

A characterization of the value of zero-sum two-person games

For the family D, consisting of those zero-sum two-person games which have a value, the value-function on D is characterized by four properties called objectivity, monotony, symmetry and sufficiency.     

Scheduling jobs,with exponentially distributed processing times,on two machines of a flow shop

This paper treats the problem of sequencing n jobs on two machines in a “flow shop.” (That is, each job in the shop is required to flow through the same sequence of the machines.) The processing time of a given job on a given machine is assumed to be distributed exponentially, with a known mean. The objective is to minimize the expected job completion time. This paper proves an optimal ordering rule, previously conjectured by Talwar [10]. A formula is also derived through Markov Chain analysis, which evaluates the expected job completion time for any given sequence of the jobs. In addition, the performance of a heuristic rule is discussed in the light of the optimal solution.     

Numerical treatment of a class of semi-infinite programming problems

Many optimization problems occur in both theory and practice when one has to optimize an objective function while an infinite number of constraints must be satisfied. The aim of this paper in to describe methods of handling such problems numerically in an effective manner. We also indicate a number of applications.