|
Article Excerpt
In an earlier paper by Emmons [Emmons, H. 1969. One-machine sequencing to minimize certain functions of job tardiness. Oper. Res. 17 701-715], the problem of sequencing jobs on a single machine in order to minimize total tardiness was analyzed. Emmons provided three theorems for specifying precedence relations for pairs of jobs. His theorems apply when the tardiness penalty for each job grows at the same rate. Rinnooy Kan et al. [Rinnooy Kan, A. H. G., B. J. Lageweg, J. K. Lenstra. 1975. Minimizing total costs in one-machine scheduling. Oper. Res. 23 908-927] later extended Emmons's theorems to the case when job tardiness penalties can grow at different rates for different jobs. Provided here is a set of theorems, stronger than those of Rinnooy Kan et al., that more fully exploits the special properties of the weighted tardiness function, allowing for greater reduction of the solution space.
Key words: single-machine scheduling; weighted tardiness; precedence
**********
1. Problem 1 [parallel] [summation] [w.sub.j] [T.sub.j]. We consider the problem of sequencing a set N of n jobs available for processing at time t = by a continuously available machine. Associated with each job i is a required processing time [p.sub.i] > 0, a due date [d.sub.i] > 0, and a tardiness weight [w.sub.i] > 0. The problem is to find a sequence that minimizes T = [summation over (i[member of]N)] [w.sub.i] max{0, [C.sub.i] - [d.sub.i]},
where [C.sub.i] represents the scheduled completion time for job i. In the notation of Graham et al. [11], this problem is referred to as 1[parallel] [summation] [w.sub.j] [T.sub.j]. The problem is strongly NP-hard (e.g., see Lawler [14]), thus requiring enumeration procedures for its solution. In that vein, precedence (dominance) theorems can play a key role.
It is important to note here at the outset that 1 [parallel] [summation] [w.sub.j] [T.sub.j] is not only a fundamentally difficult problem, but that it is also a fundamentally important one. Meeting customer due dates is a central issue in virtually all industrial operations, be they in the manufacturing sector or the service sector, and remains a central issue from any perspective within a network of operations, whether it is an individual firm, a department within a firm, or an entire collection of firms comprising a supply chain.
2. Historical perspective and motivation. Arguably, one of the most fruitful basic research results for the unweighted tardiness problem has been the three precedence theorems developed by Emmons [7] for specifying precedence constraints between pairs of jobs. For over 30 years, application of these classic theorems has served as a major scheme in support of solution procedures for solving tardiness problems on a practical scale. Emmons's three theorems have been used in virtually every major published search algorithm developed for scheduling to minimize job tardiness. The theorems specify a hypothesis in the form of a condition comparing the prior properties (e.g., processing times, due dates) of two given jobs j and k and provide a conclusion of the type: "If (Hypothesis), then there exists an optimum schedule in which job j precedes job k." Thus, when such a condition is met, it is unnecessary to consider schedules in which k precedes j (schedules in which j precedes k form a dominant set), and the search space can be approximately halved.
2.1. Agreeable, proportional, and arbitrary weights. Emmons's theorems apply to the case in which all jobs are of equal importance. However, as Vepsalainen and Morton [29] point out, the cost of tardiness, such as loss of customer good will, lost future sales, or rush shipping costs, can vary significantly among customers and orders; therefore, the more general criterion of weighted tardiness is clearly more relevant in industrial scheduling than simple (unweighted) tardiness. A good example application of the weighted tardiness criterion is semiconductor manufacturing, as recently reported by Mason et al. [17].
Probably because of its difficulty, relatively few researchers have published analytical results for weighted tardiness. They include Rinnooy et al. [21], Lawler [14], Arkin and Roundy [3], and Szwarc and Liu [25]. Lawler provided a pseudopolynomial algorithm for the case in which tardiness weights are agreeable, that is, given two jobs i and j with processing times [p.sub.i] and [p.sub.j] and tardiness weights [w.sub.i] and [w.sub.j], [p.sub.i] < [p.sub.j] [??] [w.sub.i] [greater than or equal to] [w.sub.j] and provided the following theorem:
LAWLER. For 1[parallel] [summation] [w.sub.j] [T.sub.j] if [p.sub.j] [less than or equal to] [p.sub.k], [w.sub.j], and [d.sub.j] [less than or equal to] [d.sub.k], then j precedes k in an optimum sequence.
Both Arkin and Roundy [3] and Szwarc and Liu [25] studied the case in which tardiness weights are proportional to job processing times. Arkin and Roundy provided a pseudopolynomial algorithm and a family of sequencing rules for this case. Szwarc and Liu provided three rules for specifying the optimum order in which two jobs are to be processed, given that they are to appear adjacent in the schedule, and a method for employing these rules in a decomposition algorithm.
Arkin and Roundy argue that one would expect the opposite of the agreeable weight situation of Lawler. That is, jobs with larger required processing times would more likely command higher importance--i.e., weights proportional to processing times. The idea that the bigger the job, the higher the weight may be valid in many cases, but take, for example, the case of components for assembly where the opportunity cost of a tardy component might be the lost revenue or delay cost of the entire assembly. The more general case of arbitrary weights would certmore universally applicable. With this as the objective, Rachamadugu [20] and, more recently,Akturk and Yildirim [2] and Kanet and Li [12], provided local dominance properties; that is, rules for specifying the order for two jobs given that they are to be adjacent in the schedule when the weights are arbitrary.
Vepsalainen and Morton [29] developed and tested an effective greedy heuristic (the so-called "apparent tardiness cost" rule) for specifying the sequence of jobs when weighted tardiness is the criterion and the weights are arbitrary. More recently, Lee et al. [16] extended this approach to the case when job setup times are present. Mason et al. [17] used the apparent tardiness rule as the kernel to their heuristic approach for scheduling in the semiconductor industry. Most recently, Kanet and Li [13] developed and tested a new heuristic "weighted modified due date" (WMDD), an extension of the earlier work of Baker and Bertrand [4] and Baker and Kanet [5], and found it to compare favorably with the rule of Vepsalainen and Morton [29].
2.2. The potential power of precedence theorems. Using notations similar to those of Emmons [7] and Rinnooy Kan et al. [21], define P(Q) = [[summation].sub.i[member of]Q [P.sub.i] for any set of jobs Q. Define the notation Q' for Q [subset or not equal to] N as Q' = N - Q. Define the sets [B.sub.i], [A.sub.i], as the sets of jobs known to precede i, or follow i, respectively, in some optimum sequence. In the analysis to follow, we are generally interested in establishing a precedence relation between pairs of jobs j, k such that j precedes k in some optimum sequence; i.e., we are looking for conditions that allow the assignment of j to [B.sub.k], (and thus k to [A.sub.j],). In the development that follows, we shall use the notation "j [??] k" to mean "j precedes k in some optimum sequence," or equivalently, "There exists an optimum sequence in which j precedes...
|
