Minimizing mean absolute deviation of completion times about a common due date

We consider a single machine scheduling problem in which the objective is to minimize the mean absolute deviation of job completion times about a common due date. We present an algorithm for determining multiple optimal schedules under restrictive assumptions about the due date, and an implicit enumeration procedure when the assumptions do not hold. We also establish the similarity of this problem to the two parallel machines mean flow time problem.     

Minimizing the weighted sum of quadratic completion times on a single machine

This article discusses the scheduling problem of minimizing the weighted sum of quadratic completion times on a single machine. It establishes links between orderings of adjacent and nonadjacent jobs that lead to a powerful branch and bound method. Computational results show that this method clearly outperforms the state of the art algorithm. © 1995 John Wiley & Sons. Inc.     

Minimizing flow time on a single machine with job classes and setup times

We examine the static sequencing problem of ordering the processing of jobs on a single machine so as to minimize the average weighted flow time. It is assumed that all jobs have zero ready times, and that the jobs are grouped into classes with the property that setup tasks are only required when processing switches from jobs of one class to jobs of another class. The time required for each setup task is given by the sum of a setdown time from the previous class and a setup time for the new class. We show that an algorithm presented in the literature for solving a special case of this problem gives suboptimal solutions. A number of properties of the optimal solution are derived, and their use in algorithms is evaluated. Computational results are presented for both a branch-and-bound procedure and a simpler depth-first search.     

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.     

The parallel machine min-max weighted absolute lateness scheduling problem

Given a set of jobs, a processing time and a weight for each job, several parallel and identical machines, and a common due date that is not too early to constrain the scheduling decision, we want to find an optimal job schedule so as to minimize the maximum weighted absolute lateness. We show that this problem is NP-complete even for the single-machine case, and is strongly NP-complete for the general case. We present a polynomial time heuristic for this problem and analyze its worst-case performance. Empirical testing of the heuristic is reported, and the results suggest that the performance is asymptotically optimal as the number of jobs tends to infinity. © 1994 John Wiley & Sons, Inc.     

Minimizing the average deviation of job completion times about a common due date

This paper considers a single-machine scheduling problem in which penalities occur when a job is completed early or late. The objective is to minimize the total penalty subject to restrictive assumptions on the due dates and penalty functions for jobs. A procedure is presented for finding an optimal schedule.     

Single-machine scheduling to minimize absolute deviation of completion times from a common due date

The article considers a single-machine n-job scheduling problem to minimize the sum of absolute lateness given a common due date. Two models are defined depending on whether the start time t₀ of schedules is arbitrary or fixed. Conditions are provided when those two models coincide. The developed branch-and-bound procedure is tested on nine known examples from the literature (6 ⩽ n ⩽ 14) and 90 medium-size random problems (15 ⩽ n ⩽ 25) with a fixed t₀.     

Minimizing weighted earliness and tardiness penalties in single‐machine scheduling with idle time permitted

In this paper, a single‐machine scheduling problem with weighted earliness and tardiness penalties is considered. Idle time between two adjacent jobs is permitted and due dates of jobs could be unequal. The dominance rules are utilized to develop a relationship matrix, which allows a branch‐and‐bound algorithm to eliminate a high percentage of infeasible solutions. After combining this matrix with a branching strategy, a procedure to solve the problem is proposed. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 760–780, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10039     

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     

Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date

We consider a single-machine scheduling problem in which all jobs have the same due date and penalties are assessed for both early and late completion of jobs. However, earliness and tardiness are penalized at different rates. The scheduling objective is to minimize either the weighted sum of absolute deviations (WSAD) or the weighted sum of squared deviations (WSSD). For each objective we consider two versions of the problem. In the unconstrained version an increase in the due date does not yield any further decrease in the objective function. We present a constructive algorithm for the unconstrained WSAD problem and show that this problem is equivalent to the two-parallel, nonidentical machine, mean flow-time problem. For the unconstrained WSSD and the constrained WSAD and WSSD problems we propose implicit enumeration procedures based on several dominance conditions. We also report on our computational experience with the enumeration procedures.     

Minimization of expected variance of completion times on single machine for stochastic jobs

This article deals with the problem of scheduling jobs with random processing times on single machine in order to minimize the expected variance of job completion times. Sufficient conditions for the existence of V-shaped optimal sequences are derived separately for general and ordered job processing times. It is shown that when coefficient of variation of random processing times are bounded by a certain value, an optimal sequence is V-shaped. © 1997 John Wiley & Sons, Inc.     

Minimizing the sum of absolute lateness in single-machine and multimachine scheduling

Kanet addressed the problem of scheduling n jobs on one machine so as to minimize the sum of absolute lateness under a restrictive assumption on their common due date. This article extends the results to the problem of scheduling n jobs on m parallel identical processors in order to minimize the sum of absolute lateness. Also, a heuristic algorithm for a more general version with no restriction on the common due date, for the problem of n-job single-machine scheduling is presented and its performance is reported.     

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.     

Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine

We examine a class of single-machine scheduling problems with sequence-dependent setup times that arise in the context of semiconductor test operations. We present heuristics for the problems of minimizing maximum lateness with dynamic arrivals and minimizing number of tardy jobs. We exploit special problem structure to derive worst-case error bounds. The special problem structure also enables us to derive dynamic programming procedures for the problems where all jobs are available simultaneously.     

Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine

This paper tackles the general single machine scheduling problem, where jobs have different release and due dates and the objective is to minimize the weighted number of late jobs. The notion of master sequence is first introduced, i.e., a sequence that contains at least an optimal sequence of jobs on time. This master sequence is used to derive an original mixed‐integer linear programming formulation. By relaxing some constraints, a Lagrangean relaxation algorithm is designed which gives both lower and upper bounds. The special case where jobs have equal weights is analyzed. Computational results are presented and, although the duality gap becomes larger with the number of jobs, it is possible to solve problems of more than 100 jobs. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 50: 2003     

Scheduling of a single machine to minimize total weighted completion time subject to release dates

In this paper the n/1/r_j Σ_j w_j C_j problem under the assumptions of nonpreemptive sequencing and sequence independent processing times is investigated. After pointing out the fundamental properties, some dominance sufficient conditions among sequences are obtained and a branch and bound algorithm is proposed. Computational results are reported and discussed.     

Minimizing the sum of weighted completion times of n-independent jobs when resource availability varies over time: Performance of a simple priority rule

In this article our objective is to evaluate the performance of a WSPT (weighted shortest processing time) rule for scheduling n independent jobs where the resources to process these jobs vary over time and a job can be processed by several processors simultaneously. This problem was raised by Baker and Nuttle [2]. A linear-programming (LP) model is formulated to obtain a lower bound on the minimum value of the weighted completion times. The purpose of the model is to provide a basis for evaluating the WSPT heuristic. 1000 experiments were performed using different resource profiles to test the performance of WSPT. Using WSPT, the weighted completion times were found to be, on the average, 0.2% away from their LP lower bounds.     

Minimizing mean tardiness and earliness in single-machine scheduling problems with unequal due dates

We consider a single-machine scheduling problem with the objective of minimizing the mean (or equivalently, total) tardiness and earliness when due dates may differ among jobs. Some properties of the optimal solution are discussed, and these properties are used to develop both optimal and heuristic algorithms. Results of computational tests indicate that optimal solutions can be found for problems with up to 20 jobs, and that two of the heuristic procedures provide optimal or very near optimal solutions in many instances. © 1994 John Wiley & Sons, Inc.     

Two machine flow shop scheduling problems with sequence dependent setup times: A dynamic programming approach

This paper considers the two different flow shop scheduling problems that arise when, in a two machine problem, one machine is characterized by sequence dependent setup times. The objective is to determine a schedule that minimizes makespan. After establishing the optimally of permutation schedules for both of these problems, an efficient dynamic programming formulation is developed for each of them. Each of these formulations is shown to be comparable, from a computational standpoint, to the corresponding formulation of the traveling salesman problem. Then, the relative merits of the dynamic programming and branch and bound approaches to these two scheduling problems are discussed.