Makespan minimization for m parallel identical processors

We introduce an algorithm, called TMO (Two-Machine Optimal Scheduling) which minimizes the makespan for two identical processors. TMO employs lexicographic search in conjunction with the longest-processing time sequence to derive an optimal schedule. For the m identical parallel processors problem, we propose an improvement algorithm, which improves the seed solution obtained by any existing heuristic. The improvement algorithm, called Extended TMO, breaks the original m-machine problem into a set of two-machine problems and solves them repeatedly by the TMO. A simulation study is performed to evaluate the effectiveness of the proposed algorithms by comparing it against three existing heuristics: LPT (Graham, [11]), MULTIFIT (Coffman, Garey, and Johnson, [6]), and RMG (Lee and Massey, [17]). The simulation results show that: for the two processors case, the TMO performs significantly better than LPT, MULTIFIT, and RMG, and it generally takes considerably less CPU time than MULTIFIT and RMG. For the general parallel processors case, the Extended TMO algorithm is shown to be capable of greatly improving any seed solution. © 1995 John Wiley & Sons, Inc.     

Scheduling about a large common due date with tolerance to minimize mean absolute deviation of completion times

In this article the problem of minimizing the mean absolute deviation (MAD) of job completion times about an unrestricted given common due date with tolerance in the n-job, single-machine scheduling environment is considered. We describe some optimality conditions and show that the unrestricted version of the MAD problem with an arbitrary due date tolerance is polynomial by proposing a polynomial-time algorithm for identifying an optimal schedule. © 1994 John Wiley & Sons, Inc.     

A hybrid algorithm for the one machine sequencing problem to minimize total tardiness

In a recent paper, Hamilton Emmons has established theorems relating to the order in which pairs of jobs are to be processed in an optimal schedule to minimize the total tardiness of performing n jobs on one machine. Using these theorems, the algorithm of this paper determines the precedence relationships among pairs of jobs (whenever possible) and eliminates the first and the last few jobs in an optimal sequence. The remaining jobs are then ordered by incorporating the precedence relationships in a dynamic programming framework. Propositions are proved which considerably reduce the total computation involved in the dynamic programming phase. Computational results indicate that the solution time goes up less than linearly with the size (n) of the problem. The median solution time for solving 50 job problems was 0.36 second on UNIVAC 1108 computer.     

Open-shop scheduling problems with dominated machines

This article deals with special cases of open-shop scheduling where n jobs have to be processed by m, m ?3, machines to minimize the schedule length. The main result obtained is an O(n) algorithm for the three-machine problem with a dominated machine.     

Scheduling jobs and maintenance activities on parallel machines

Most machine scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines need to be maintained and hence may become unavailable during certain periods. In this paper, we study the problem of processing a set of n jobs on m parallel machines where each machine must be maintained once during the planning horizon. Our objective is to schedule jobs and maintenance activities so that the total weighted completion time of jobs is minimized. Two cases are studied in this paper. In the first case, there are sufficient resources so that different machines can be maintained simultaneously if necessary. In the second case, only one machine can be maintained at any given time. In this paper, we first show that, even when all jobs have the same weight, both cases of the problem are NP-hard. We then propose branch and bound algorithms based on the column generation approach for solving both cases of the problem. Our algorithms are capable of optimally solving medium sized problems within a reasonable computational time. We note that the general problem where at most j machines, 1 ≤ j ≤ m, can be maintained simultaneously, can be solved similarly by the column generation approach proposed in this paper. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 145–165, 2000     

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     

Optimal assignment of high multiplicity flight plans to dispatchers

This paper addresses the problem of finding a feasible schedule of n jobs on m parallel machines, where each job has a deadline and some jobs are preassigned to some machine. This problem arises in the daily assignment of workload to a set of flight dispatchers, and it is strongly characterized by the fact that the job lengths may assume one out of k different values, for small k. We prove the problem to be NP‐complete for k = 2 and propose an effective implicit enumeration algorithm which allows efficiently solution a set of real‐life instances. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 359–376, 2000     

Rectilinear m-Center problem

In this article we consider the unweighted m-center problem with rectilinear distance. We preent an O(n^m–2 log n) algorithm for the m-center problem where m ≥ 4.     

A single-machine scheduling problem with random processing times

We consider the problem of scheduling n jobs with random processing times on a single machine in order to minimize the expected variance of the completion times. We prove a number of results, including one to the effect that the optimal schedule must be V shaped when the jobs have identical means or variances or have exponential processing times.     

An extension of the (szwarc) truck assignment problem

In this journal in 1967. Szware presented an algorithm for the optimal routing of a common vehicle fleet between m sources and n sinks with p different types of commodities. The main premise of the formulation is that a truck may carry only one commodity at a time and must deliver the entire load to one demand area. This eliminates the problem of routing vehicles between sources or between sinks and limits the problem to the routing of loaded trucks between sources and sinks and empty trucks making the return trip. Szwarc considered only the transportation aspect of the problem (i. e., no intermediate points) and presented a very efficient algorithm for solution of the case he described. If the total supply is greater than the total demand, Szwarc shows that the problem is equivalent to a (mp + n) by (np + m) Hitchcock transportation problem. Digital computer codes for this algorithm require rapid access storage for a matrix of size (mp + n) by (np + m); therefore, computer storage required grows proportionally to p². This paper offers an extension of his work to a more general form: a transshipment network with capacity constraints on all arcs and facilities. The problem is shown to be solvable directly by Fulkerson's out-of-kilter algorithm. Digital computer codes for this formulation require rapid access storage proportional to p instead of p². Computational results indicate that, in addition to handling the extensions, the out-of-kilter algorithm is more efficient in the solution of the original problem when there is a mad, rate number of commodities and a computer of limited storage capacity.     

Single- and multiple-processor models for minimizing completion time variance

This article concerns the scheduling of n jobs around a common due date, so as to minimize the average total earliness plus total lateness of the jobs. Optimality conditions for the problem are developed, based on its equivalence to an easy scheduling problem. It seems that this problem inherently has a huge number of optimal solutions and an algorithm is developed to find many of them. The model is extended to allow for the availability of multiple parallel processors and an efficient algorithm is developed for that problem. In this more general case also, the algorithm permits great flexibility in finding an optimal schedule.     

One machine sequencing to minimize mean flow time with minimum number tardy

The problem of sequencing n jobs on one machine is considered, under the multiple objective of minimizing mean flow time with the minimum number of tardy jobs. A simple procedure is first proposed to schedule for minimum flow time with a specified subset of jobs on time. This is used in conjunction with Moore's Algorithm in a simple heuristic producing good and often optimal schedules. A branch-bound algorithm is presented to produce the optimal schedule efficiently with the help of several theorems which eliminate much branching.     

Confidence intervals in discrete event simulation: A comparison of replication and batch means

Suppose that we have enough computer time to make n observations of a stochastic process by means of simulation and would like to construct a confidence interval for the steady-state mean. We can make k independent runs of m observations each (n=k.m) or, alternatively, one run of n observations which we then divide into k batches of length m. These methods are known as replication and batch means, respectively. In this paper, using the probability of coverage and the half length of a confidence interval as criteria for comparison, we empirically show that batch means is superior to replication, but that neither method works well if n is too small. We also show that if m is chosen too small for replication, then the coverage may decrease dramatically as the total sample size n is increased.     

Scheduling maintenance and semiresumable jobs on a single machine

The majority of scheduling literature assumes that the machines are available at all times. In this paper, we study single machine scheduling problems where the machine maintenance must be performed within certain intervals and hence the machine is not available during the maintenance periods. We also assume that if a job is not processed to completion before the machine is stopped for maintenance, an additional setup is necessary when the processing is resumed. Our purpose is to schedule the maintenance and jobs to minimize some performance measures. The objective functions that we consider are minimizing the total weighted job completion times and minimizing the maximum lateness. In both cases, maintenance must be performed within a fixed period T, and the time for the maintenance is a decision variable. In this paper, we study two scenarios concerning the planning horizon. First, we show that, when the planning horizon is long in relation to T, the problem with either objective function is NP-complete, and we present pseudopolynomial time dynamic programming algorithms for both objective functions. In the second scenario, the planning horizon is short in relation to T. However, part of the period T may have elapsed before we schedule any jobs in this planning horizon, and the remaining time before the maintenance is shorter than the current planning horizon. Hence we must schedule one maintenance in this planning horizon. We show that the problem of minimizing the total weighted completion times in this scenario is NP-complete, while the shortest processing time (SPT) rule and the earliest due date (EDD) rule are optimal for the total completion time problem and the maximum lateness problem respectively. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 845–863, 1999     

The single-machine absolute-deviation early-tardy problem with random completion times

We consider sequencing n jobs on a single machine subject to job completion times arising from either machine breakdowns or other causes. The objective is to minimize an expected weighted combination of due dates, completion times, earliness, and tardiness penalties. The determination of optimal distinct due dates or optimal common due dates for a given schedule is investigated. The scheduling problem for a fixed common due date is considered when random completion times arise from machine breakdowns. The optimality of a V-shaped about (a point) T sequence is established when the number of machine breakdowns follows either a Poisson or a geometric distribution and the duration of a breakdown has an exponential distribution. © 1996 John Wiley & Sons, Inc.     

On the uncapacitated K‐commodity network design problem with zero flow‐costs

Extending Sastry's result on the uncapacitated two‐commodity network design problem, we completely characterize the optimal solution of the uncapacitated K‐commodity network design problem with zero flow costs for the case when K = 3. By solving a set of shortest‐path problems on related graphs, we show that the optimal solutions can be found in O(n³) time when K = 3, where n is the number of nodes in the network. The algorithm depends on identifying a list of “basic patterns”; the number of basic patterns grows exponentially with K. We also show that the uncapacitated K‐commodity network design problem can be solved in O(n³) time for general K if K is fixed; otherwise, the time for solving the problem is exponential. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Note: “Simultaneous optimization of efficiency and performance balance measures in single-machine scheduling problems”

n independent jobs are to be scheduled nonpreemptively on a single machine so as to minimize some performance measure. Federgruen and Mosheiov [2] show that a large class of such scheduling problems can be optimized by solving either a single instance or a finite sequence of instances of the so-called SQC problem, in which all the jobs have a fixed or controllable common due date and the sum of general quasiconvex functions of the job completion times is to be minimized. In this note we point out that this is not always true. In particular, we show that the algorithm proposed in [2] does not always find a global optimal schedule to the problem of minimizing the weighted sum of the mean and variance of job completion times. © 1996 John Wiley & Sons, Inc.     

An algorithm for 0-1 multiple-knapsack problems

The 0-1 multiple-knapsack problem is an extension of the well-known 0-1 knapsack problem. It is a problem of assigning m objects, each having a value and a weight, to n knapsacks in such a way that the total weight in each knapsack is less than its capacity limit and the total value in the knapsacks is maximized. A branch-and-bound algorithm for solving the problem is developed and tested. Branching rules that avoid the search of redundant partial solutions are used in the algorithm. Various bounding techniques, including Lagrangean and surrogate relaxations, are investigated and compared.     

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000     

A heuristic routine for solving large loading problems

The loading problem involves the optimal allocation of n objects, each having a specified weight and value, to m boxes, each of specified capacity. While special cases of these problems can be solved with relative ease, the general problem having variable item weights and box sizes can become very difficult to solve. This paper presents a heuristic procedure for solving large loading problems of the more general type. The procedure uses a surrogate procedure for reducing the original problem to a simpler knapsack problem, the solution of which is then employed in searching for feasible solutions to the original problem. The procedure is easy to apply, and is capable of identifying optimal solutions if they are found.