ALGORITHMS FOR SINGLE MACHINE SCHEDULING PROBLEMS MINIMIZING TARDINESS AND EARLINESS Candace A. Yano Yeong-Dae Kim Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 86-40 October 1986

ALGORITHMS FOR SINGLE MACHINE SCHEDULING PROBLEMS MINIMIZING TARDINESS AND EARLINESS ABSTRACT Most scheduling research has been done with one criterion, but in some situations two or more criteria should be considered at the same time. In this paper, single machine scheduling problems with the objective of minimizing the sum of tardiness and earliness are considered. An algorithm for the optimal completion times of jobs is developed, and some properties of optimal sequences are discussed. These properties are used to develop both optimal and heuristic procedures. Computational results for problems with up to 40 jobs are reported.

ALGORITHMS FOR SINGLE MACHINE SCHEDULING PROBLEMS MINIMIZING TARDINESS AND EARLINESS In many practical scheduling problems, costs arising from both earliness and tardiness of the individual jobs must be minimized. For example, in production systems in which there are shipping dates for orders, inventory carrying costs are incurred if jobs are finished earlier than the shipping dates, and shortage costs (penalty costs or backorder costs) are incurred if jobs are finished later than the shipping dates. To minimize total costs, tardiness and earliness of jobs should be minimized. In this paper earliness and tardiness are defined as max(d.- C., 0) and max(Ci- d., 0) respectively, where d. is the due date and C. is the completion time of job i. 1 There has been some research for the single machine scheduling problems with multiple performance criteria related to inventory carrying costs and shortage costs. Emmons(1975a) develops a branch-and-bound algorithm for the bicriterion scheduling problem in which minimizing the number of tardy jobs is the primary objective and minimizing mean flow time is the secondary objective. Emmons(1975b) also gives some properties of solutions for the problems with the dual criteria of mean flow time and maximum penalty, where the penalty reflects the cost of completing a job at a certain time. Later, Van Wassenhove and Gelders(1980) consider the bicriterion problem to minimize holding cost and maximum tardiness. The set of efficient points is characterized and a pseudo-polynomial algorithm to enumerate all these points is given. These objectives are combined as a single objective which is a convex combination of the two in Sen and Gupta(1983). Algorithms to generate efficient points are developed for multicriterion performance measures in other research such as Van Wassenhove and Baker(1982) for time/cost trade-offs, Lin(1983) for mean tardiness and mean flow time, and Nelson et al.(1986) for mean flow time, maximum tardiness, and number of tardy jobs. Very few papers have been published which consider tardiness and earliness. 1

Sidnev(1977) presents an optimal algorithm where the objective is to minimize the maximum of the costs of earliness and those of tardiness, where the costs are nondecreasing functions of earliness and tardiness, respectively. Following this, a more efficient algorithm was developed for the same problem by Lakshminarayan et al.(1978). In these two papers earliness is defined as the difference between the target start time and the actual start time. Townsend(1978) develops a branch-and-bound procedure for the objective of minimizing total penalty, where the penalty of each job is expressed as a quadratic function of completion time. Since tardiness plus earliness is a piecewise linear convex function of completion time, his problem is similar to ours in some sense. Using a similar bounding technique Gupta and Sen(1983) presents a branch-and-bound and a heuristic algorithms for minimizing a quadratic function of job lateness. Here they do not allow machines to be idle. Differently from the others, Panwalkar et al.(1982) consider the problem in which the due dates are decision variables. They develop a polynomial algorithm to find the due dates and the sequence to minimize the costs resulting from due dates, earliness, and tardiness. In this paper two problems are considered, which are n/1//T+E and n/i// Z(r.T.+.E.). Here n/m/A/B indicates the scheduling problem in which n, m are the 11 11 numbers of jobs and machines respectively, A is the flow discipline, and B is the performance criterion. T. and E. refer to the tardiness and the earliness of job i, and r. 1 1 1 and E. are their weights. Therefore these problems are single machine scheduling problems with objectives of minimizing mean tardiness plus earliness (ri.=.=1 for all i), and minimizing weighted sum of tardiness plus earliness where the weights of tardiness and earliness of each job are different, respectively. The first problem is a special case of the second. Note that the mean tardiness problem is a subset of the second problem but it is unrelated to the first. The relationships among these and other related problems are shown in Figure 1. A special case of the n/l//T+E problem, which is n/l//T+E with equal due dates, has been discussed in Kanet(1981), Sundararaghavan and Ahmed(1984), and 2

Bagchi et al.(1986). Even though this problem may not occur frequently in practice, it may be important from a theoretical perspective. If this problem is NP-complete, all the problems mentioned in this paper are NP-complete since this problem is a special case of the others. Section 1 presents an algorithm for determining completion times of jobs for a given sequence. In Section 2, some properties of optimal job sequences for the n/l//T+E problem are discussed and a branch and bound algorithm and a heuristic algorithm are presented. Section 3 discusses the general problem, i.e., n/l//Z(r.T. + e.E.), and computational results are presented in Section 4. Finally some concluding remarks appear in Section 5. 1. DETERMINING OPTIMAL COMPLETION TIME FOR EACH JOB IN A SEQUENCE When a sequence is given, an optimal schedule can be obtained easily by using a linear program(LP), since the technical constraints(precedence relationships) are all given. An LP formulation is Min Z (E. + T. ) 1 1 s.t. d.- C. =E.-T., forall i 1 1 1 1 (i) C(i-c 1) > (i) i=2ton Ci, Ei, Ti. 0, for all i where (i) is i-th job in the given sequence, P(i) is processing time for the i-th job, and the other notation is the same as before. Earliness and tardiness of a job can be expressed by the difference between the completion time and the given due date for the job as in the first constraint. The second constraint assures that no more than one job can be processed on the machine at any time. Since a sequence is given, disjunctive constraints are not necessary. Note that there are 3n variables and 2n-1 constraints in this LP formulation. However, the best known algorithm 3

for LPs requires pseudo-polynomial time. A more efficient algorithm which is strongly polynomial is presented here. The following notation is used in this algorithm. Throughout the remainder of this section subscript i refers to the i-th job in the given sequence. Pi: processing time for the i-th job in the sequence d.: due date of the i-th job in the sequence C.: completion time of i-th job in the sequence S. slack time(machine idle time) between job i and job i+ 1 1 S= C. - Pi+ - C G. gradient of T + E (tardiness plus earliness) of job i when job i is moved 1 unit time later D. = max (d. - C. 0) 1 1 1 TG: gradient of T + E of a partial sequence when the job being considered is moved 1 time unit later at a stage of the algorithm::.-. ii':'. A ihe first job in partial schedule at any stage of the algorithm i-i u. Z p., the earliest possible time job i can start 1 k=1 Note that TG for any partial sequence with no inserted idle time between jobs is a nondecreasing step function of the completion time, and therefore the sum of earliness and tardiness for the partial sequence is piecewise linear convex as long as there is idle time following the partial sequence. Now the algorithm can be stated. In this algorithm, the jobs are considered in reverse order of the given sequence. Using G. and TG, we shift jobs as late as possible without increasing T +E. This provides more time for the jobs which are to be placed prior to them. 4

Algorithm 1. (0) Initialization Let C =dn, s=Cn -pn G 1, TG= G S = Let j = n- 1, and goto(1). (1) If j = 0, go to (4). If j > 0, if s d., go to (2), J if s < d., let D. =d. s, C. s, G. = -1, J J j J J TG = TG + G., and go to (3). J (2) Let C. = d., s = C. -p., S. = s -d., G.= 1. J J J J J J J Reset TG = G.. J Let j = j - 1,and go to (1). (3) If TG > 0,let j = j- 1, and go to (1). If TG s 0, shift jobs to right until further shifting is not possible without making TG positive, and update values of Ci, Di, s, Gi, TG if needed. Let j = j - 1, and go to (1). (4) If S1 > 0, stop. The resulting schedule is optimal. Otherwise, shift jobs to right to make S1 = 0. Terminate. U When we visit step 2, there is a positive slack time between job j and job j + 1. At this time we reset TG = G., since job j-1 would not be affected by the jobs after j. At step 3, if TG > 0, we cannot reduce T + E of the jobs scheduled so far by shifting jobs to the right or left. If TG c 0, shifting jobs to right does not increase (and may decrease) T+E of the jobs scheduled. This shift increases TG. When the amount of shift is equal to S.> 0 for some i, the slack time between jobs i and i + 1 becomes 0 and TG should be recalculated by adding the gradients of jobs in the partial sequence which includes job i and has no inserted slack time between jobs. Figure 2 shows how this algorithm works in a simple example. The given sequence in this example is (1,2,3,4,5,6), and the problem data are shown as a figure at the top of Figure 2. The rectangles denote jobs and their widths denote the processing times of jobs. 5

The following theorem shows the efficiency and optimality of this algorithm. Theorem 1. Algorithm 1 obtains an optimal schedule when a sequence is given, and the worst case computational complexity is O(n2). Proof. Since the sequence is given, we can only shift jobs forward or backward without changing the order. Consider any subset of jobs with no inserted slack time between jobs in the solution resulting from Algorithm 1. Since Z ( E. + T. ) for the 1 1 subset is piecewise linear convex, and in the solution the jobs in the subset have been shifted up to the point where TG becomes positive (from zero or negative), we cannot improve the solution by shifting the jobs in either direction. Therefore the solution is optimal. If job j is considered and we visit step 3, TG=0. To find the amount of shift that makes TG positive, we only have to find the minimum value among S. and D. for j+p 1 i =j, j + 1, * *, j + p, where jobs j, j + 1, *, j + p are in the same subset described as above. This needs effort of O(p) where p is not greater than n-j. After this we need to update the values C., D., Gi, TG, which needs O(n-j) effort at most. Therefore every visit to step 3 needs O(n) effort. At step 4, if a shift is needed we can do it in O(n) as follows. Calculate u. and C.- Pi and find k = min [ i | ui < C - p ]. Reset 1 1 1 1 1 1 C. = u.+ Pi for i=1,2, *,k-1. This needs O(k) effort, and k ~ n. Steps 1 and 2 need 0(1) effort for each visit. Every step can be visited at most n times in the entire algorithm. Therefore the overall computational complexity of this algorithm is O(n2) in terms of basic arithmetical operations such as additions, comparisons, or look-ups. ~ We now have an algorithm to determine the optimal completion times of jobs for a given sequence. It can be used as a subroutine in determining good or optimal sequences of jobs. In the next section we develop properties of the optimal job sequences. 6

2. ALGORITHMS FOR n/l//T+E PROBLEM In this section, algorithms for the n/1//T+E problem are presented. Since a polynomial algorithm has not been found for this problem, a branch-and-bound algorithm and a heuristic algorithm are developed. First some properties of the optimal sequence of jobs which are useful for these algorithms will be discussed. Lemma 2. If there is a conflict between 2 and only 2 jobs when the jobs are placed as C. =d. for both jobs, and if pi< p., then the following statements are true. (Case 1) If d.> d., then job j should precede job i. 1 (Case 2) If d.< d. 1 J (Subcase 2.1) If i + (d. - di) - p., then i should precede j. (Subcase 2.2) If Pi+ (d. - di) < pj, let A = p. - p- (d. - d.). 3 1 3 3 1 1 If A < d. - d., i should precede j, otherwise, j should precede i. (See Figure 3.) 3 1 Proof. Let TE.. = Min.. [T. +E.+ T. + E. ], where i precedes j. 13 1 i 1 j j Using algorithm 1 we can get TE.. and TE... (Case 1) TE.. = pj -(d- d.), TE..= i - (di- d). Since p< pj, TEji.. < TE... i J J31 1 (Case 2) TE..= p - (d. - d.), TE..= pi+ (d. - d). (Subcase 2.1) Since Pi< p., and d.< d., TE..>i p. TE... (Subcase 2.2) When A d. - d., TE..= A + p.i pi+ (d. - d.) TE... J i 13 J 1 ji When A > d. - d, TE..= A+ p i + (d. - d.) TE... 3 1 13 1 J J1 By considering all cases in the proof of Lemma 2, and by using Algorithm 1, the following corollaries can be proven easily. They are, therefore, stated without proof. 7

Corollary 3. If there is a conflict between 2 jobs when the jobs are placed as C. =d. for both jobs, the sum of tardiness and earliness is not less than the time during which the two jobs overlap. Corollary 4. In the same situation as in corollary 3, there may be alternate optimal schedules and there exists an optimal schedule such that either C. =d. or C. =d.. 1 1 J J These properties are useful in getting bounds for subproblems in the B&B algorithm. The next property can be used for pruning some subproblems. This property shows some dominance rules of sequences by considering adjacent jobs in cases where both jobs should be finished earlier than their due dates, or where both jobs are started after their due dates because of succeeding or preceding jobs. Lemma 5. In adjacent jobs i and j, (1) If there is a constraint such that t= max (Ci,C.) < min (d.,d.), then i should precede j when pi> pj, and j should precede i when P < pi. (2) If there is a constraint such that min (s.,s.) - max (d.,d.), then i should precede j when i < Pj, and j should precede i when pi> pj. (3) If there is a constraint such that min (si,sj) + min (Pi,Pj) _ max (di,dj), then i should precede j when pi< pj, and j should precede i when pi> pj, where s. is the start time of job i. (See Figure 4.) Proof. (1) TEji= d. - d.+ Pi+ 2(d - t), TE..= d. - d.+ 2(di - t) + pj, ii J 1 1 J. TE.- TE..= p. - p.. Hence the results follow. ij Ji J 1 (2) TE..ij= 2(t - d.) + 2Pi + (d. - d.) + pj, ii j 1 J J 8

TE..= 2(t - d.) + 2p. t (d. - di + Pi, ~J1 JJ p J 1 TE..- TE..= P - p.. Hence the results follow. (3) TE..= t + Pi - d.+ t P+ Pi - d., 1. 1 1 i J J TE..= t + pj+ Pi - d.+ t + p. - d., TE..- TE.. = p. - p.. Hence the results follow. U ii J I 1. Now a branch-and-bound algorithm using the above properties can be stated. Each node of the branching tree is associated with a partial sequence which will be placed at the end of the whole sequence. That is, a node at the p-th level of the tree corresponds to a partial sequence < p >, < p- 1 >, < p-2 >,. -, < 1 >, where < i > represents i-th job from the end, and one of the remaining n-p jobs is to be selected for <p+ 1>. Let J be the set of all jobs, a be a partial sequence being placed at the end of the sequence, and PS be the set of jobs in o. Algorithm 2. (A branch-and-bound algorithm) Branching Select a node with the least lower bound in branching tree for branching. Bounding (1) Bound B1 for jobs in PS B1 is the optimal solution (minimum value of Z(T.+E.) ) obtained from Algorithm 1 for the sequence a under the constraint that the earliest possible start time of the first job in PS is Z pi instead of 0. ieJ\PS (2) Bound B2 for job in J\PS B2 is the sum of the time intervals during which two or more jobs overlap, when we place all the jobs in J\PS to satisfy C.= d.. This bound can be justified by Corollary 3 justified by Corollary 3, 9

Then the lower bound of the node associated with the partial sequence a will be B=B +B2 Pruning If there is any adjacent pair of jobs i, j in the partial sequence a, such that min[ s.,s. + min[ pi, p. ] > max[ di, d. ], prune that partial sequence. This can be justified since there always exists a better sequence a* which is identical to a except for the order of jobs i and j. ~ To improve the efficiency of the algorithm the lower bounds need to be sharper(larger). The following lemma and the argument following it help to improve the lower bound B2. Lemma 6. If there are conflicts among 2 or more jobs when a set of jobs is placed as C. = d. for all i in the set, the sum of tardiness and earliness is not less than Z (k1 k>2 l)tk, where tk is the length of time during which k jobs overlap. Proof. It is obvious that the optimal objective function value for a set of jobs is not less than the sum of the objective value of the subsets of jobs which make the set itself. We can divide a set of jobs into several subsets which are separated at times when there are no overlapping jobs (such as at to in Figure 5). From the above statement, we only have to prove that Z (Th+Eh) > Z (k-l)tk ibJ i i k>2 k h k in an arbitrary subset of jobs, Jh, divided as mentioned above. We first prove that for any sequence (1),(2),. *,(r) of jobs in Jh min r(T+E) > P(2)+ P(3)+* + P(r)-( d(r)- d(1) 10

r Consider jobs (2),...(r) as one job A with processing time Z P) and due date i=2 d(). Then T+E for jobs (1),(2),. -,(r) is not less than T+E for jobs (1) and A. This is because T+E for jobs (2), *,(r-l) are all nonnegative and T+E for job (r) is equal to T + E for job A. By Corollary 4, for two adjacent jobs (1) and A, a schedule where either C(1)= d(1) or CA=d(r) is optimal. In both cases T+E for jobs (1) and r A is not less than Z p(i d- d) Next we prove that i-=2 TE - P(2)+ P(r) - ( d(r) - d(1)) - Z (k- 1)tk k=2 r Since there is no idle time, Z tk P(1) + ( d(r) - d(1) ) k=l ) (r) (1) Then r TE = Z P(k) P(1)- ( (r)- d r = Z ktk- p ()-(d(r)- d () ) k=1 P(1) (r) (1) r r = Z (k-l)tk + Z tk-p(1) ( (d(r dl)) k=2 k=l r r - Z (k-l)tk, since Z tk P(1) + (d(r) -d(1) k=2 k=l The above is true for every sequence of r jobs considered. This completes the proof. ~ The above property is described pictorially in Figure 5, where there are two subsets divided by time to. Conceptually, Lemma 6 says that jobs must be shifted far enough forward or backward in time from their respective due dates to satisfy the constraint of at most one job on the machine at a given time. The lower bound on T+E gives the minimal amount of shifting to accomplish this on the assumption that each subset of jobs can be considered separately. In general, shifting in one subset will affect other subsets, so that the given bound may not be achievable. 11

If TG and s which result from Algorithm 1 are used, the lower bound B. can be improved as follows. Consider the case where (1) there are jobs not in PS whose due date is greater than s, and (2) TG resulting from the optimal timing for PS is greater than 0. The last k jobs (with largest due time) of J\PS and the optimal schedule for the jobs in PS k incur T+E no less than Z ( d<i>- s ), where <i> is the i-th job from the end in i=l J\PS, and k is the minimum value of TG and n, the number of jobs in J\PS whose due date is greater than s. This bound can be justified as follows. If k = TG, either the k last jobs in J\PS should move to the left up to the time s, or jobs in PS should move to right, k both of which incur T+E of no less than Z ( d <i>- s ). Moreover in this case, i=1 Lemma 6 can be used to calculate T + E on the jobs not considered yet. Here the set of jobs in PS can be considered as a job whose due date is CpS, the completion time of the jobs in PS, and processing time is Cps- s. If k = n, k last jobs in J\PS should be move k to the left, which incurs T+E of no less than Z ( d -s ) <i> i=l Since the above algorithm requires exponential time in the worst case, we cannot guarantee that it is computationally tractable for larger problems. Therefore a heuristic algorithm is presented here. This algorithm uses the properties in Lemmas 2 and 5 to construct a good sequence, and uses Algorithm 1 to find an optimal timing for the sequence. By comparing all pairs of jobs using the results of Lemma 2, we can obtain rough information about the priority of each job, i.e., how many jobs should precede it. These priorities can give a good initial sequence which will be examined using dominance criteria of Lemma 5 and will be changed if needed. Algorithm 3. (A heuristic algorithm) Let a. be the label of job i. (1) Compare jobs i and j, for all possible combinations of 2 jobs, using the simple rule in Lemma 2. 12

If i precedes j, let a. = a. - 1a. = a. + 1, 1 1 j j ifj precedes i, let a. a. + 1, a. =a. - 1. 1 1 J j else, no change in a., a.. 1 J (2) Sort the jobs in ascending order of a.'s. This will be the initial sequence. (3) Obtain the optimal timing for the sequence resulted from (2) using Algorithm 1. (4) Check the conditions for dominance in Lemma 5 for adjacent pairs of jobs, and change the order if needed. Check whether T+E can be reduced when the adjacent jobs are interchanged, and change the order if needed. (5) For the sequence resulting from (4), obtain optimal timing using Algorithm 1. Terminate. ~ At step (4), the pairwise comparison of interchange can be done in two directions, forward and backward. In forward comparisons, k-th job is compared with (k+ l)th job, (k+ 2)th job, * *, until it cannot be changed any more, for k=n-l,n-2, * *,1. In backward comparisons k-th job is compared with (k-l)th job, (k-2)th job, *.., until it cannot be changed for k=2,3, *.,n. Since this requires O(n2) effort, and the other steps also require at most O(n2) effort, the overall computational complexity of this heuristic algorithm is O(n2). 3. n/l//Z(r.T. +.E.) PROBLEM In this section the general problem, n/l//Z(r.T. + e.E.) will be discussed. As in the n/ 1//T+E problem, a special case of this problem, the optimal schedule(timing) for a given sequence can be obtained by solving an LP. Algorithm 1 can also be modified to solve this problem with O(n2log n) effort. The needed modifications are: a) In step (0), G = 1 should be changed to G = r; n n n 13

b) In step (1), G.= -1 should be changed to G.= -e. j J j' c) In step (2), G.= 1 should be changed to G.= r. j J J Getting an optimal sequence for this problem is even harder than for the case of r.= e.= 1, for all i. From Lemmas 2 and 5, and Corollaries 3 and 4, a loose lower bound for Z(r.T.+ E.E.) can be presented. That is, a lower bound B2 for jobs in a set J\PS is, 11 11 B2 = t { Z min(r.,e.) - max.[ min(ri, i)] } o ie( where w is any set of overlapping jobs in J\PS, and t is the length of time during which CO jobs in c overlap, if all the jobs in J\PS are placed as C.= d.. For example, in Figure 5, 1 1 one of is (2,3,4) and t(2,3,4)= t32. Note that the terms in braces correspond to k - 1, and t corresponds to tk of Lemma 6. The lower bound B1 for jobs in PS can be calculated by the same method as in Algorithm 2. A heuristic algorithm which will not be presented in this paper can be developed using a method similar to Algorithm 3. 4. COMPUTATIONAL RESULTS A set of problems has been generated randomly for our experiment. The due dates follow a uniform distribution from 0 to a given maximum due date. The processing times have been generated from the uniform distribution such that the machine loads, i.e., the sum of these processing times divided by the maximum due date, would be between 0.6 and 1.3. The algorithms were coded in FORTRAN and run on the Amdahl 470V/8. The results are given in Tables 1 and 2. Table 1 contains the problems in which machine load is greater than 0.9, while Table 2 contains those where the machine load is less than 0.9. As can be seen in the tables, when the machine load was high (20.9) the branch-and-bound algorithm could not solve the 30 job problems and could solve less than half of eight problems with 20 jobs. However, when machine load was low(< 0.9), it could solve 5 out of 8 problems with 30 jobs. When machine load is high; earliness rarely 14

occurs, therefore the problem would look like a mean tardiness problem. From this point of view, our algorithm works better in the situations where earliness may be important, i.e., where machine load is not near 100%. In the problems where the optimal solution was found by the branch-and-bound algorithm, over 90 percent of the solutions from the heuristic algorithm were optimal solutions. In most of the other problems, the heuristic solution is same as the incumbent solution obtained by the branch-and-bound algorithm after a CPU time of 30 seconds. In only two problems was the heuristic solution proved to be suboptimal. The minimum lower bound among the subproblems left in the stack is also given in the tables. Even though this minimum lower bound is better than the incumbent solution in some problems, it is likely to increase as more branching occurs. This difference between the minimum lower bound and the incumbent solution is higher in larger problems since the depth of the branch and bound tree was limited by CPU time. Thus, the minimum lower bounds may not be indicative of optimal objective values. In summary, the heuristic procedure appears to provide optimal or near-optimal solutions in a fraction of the CPU time of the optimal procedure. 5. CONCLUSION Scheduling decisions are generally affected by a number of costs. In this paper, scheduling problems which can be used in production and inventory planning have been discussed. The problem involving tardiness and earliness as dual criteria needs not only a sequence but also an optimal timing of the sequence. A polynomial algorithm has been developed for determining the optimal completion times of jobs for a given sequence. A branch-and-bound algorithm and a heuristic algorithm have been presented to obtain the schedule (sequence and timing). For a set of randomly generated problems, the heuristic algorithm performed extremely well. There are two directions for future research on this problem. One is to develop a 15

good(polynomial) algorithm for these problems. The other is to prove NP-completeness of the problem, n/1//T+E with equal due dates, and to develop a more efficient B&B algorithm or an heuristic algorithm. In addition, extension of the results to multiple machine problems would be very useful for real applications. These problems would cover the cases where jobs have different penalties for earliness and tardiness, which occur frequently in reality. REFERENCES Bagchi, V., R.S. Sullivan, and Y.L. Chang, 1986. Minimizing Mean Absolute Deviation of Completion Times about a Common Due Date. Naval Research Logistics Quarterly, Vol.33, pp.227-240. Baker, K.R., 1974. Introduction to Sequencing and Scheduling. Wiley, New York. Emmons, H., 1975a. One Machine Sequencing to Minimize Mean Flow Time with Minimum Number Tardy. Naval Research Logistics Quarterly, Vol.22, No.3, pp.585 -592. Emmons, H., 1975b. A Note on a Scheduling Problem with Dual Criteria. Naval Research Logistics Quarterly, Vol.22, No.3, pp.615-616. Garey, M.R. and D.S. Johnson, 1979. Computers and Intractability A Guide to the Theory' of NP-Completeness, Freeman. Gupta, S.K. and T. Sen, 1983. Minimizing a Quadratic Function of Job Lateness on a Single Machine. Engineering Costs and Production Economics, Vol.7, pp. 187-194. Kanet, J.J., 1981. Minimizing the Average Deviation of Job Completion Times about a Common Due Date. Naval Research Logistics Quarterly, Vol.28, No.4, pp.643-651. Lakshiminarayan, S., R. Lakshmanan, R.L. Papineau, and R. Rochette, 1978. Optimal Single-Machine Scheduling with Earliness and Tardiness Penalties. Operations Research, Vol.26, No.4, pp.1079-1082. Lin, K.S., 1983. Hybrid Algorithm for Sequencing with Bicriteria. Journal of Optimization Theory and Applications, Vol.39, No.1, pp.905-924. Nelson, R.T., R.K. Sarin, and R.L. Daniels, 1986. Scheduling with Multiple Performance Measures: The One-Machine Case. Management Science, Vol.32, No.4, pp.464-479. Panwalkar, S.S., M.L. Smith, and A. Seidmann, 1982. Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem. Operations Research, Vol.30, No.2, pp.391-399. 16

Sen, T. and S.K. Gupta, 1983. A Branch-and-Bound Procedure to Solve a Bicriterion Scheduling Problem. IIE Transactions. Vol. 15. No. 1, pp.84-88. Sen, T. and S.K. Gupta, 1984. A State-of-Art Survey of Static Scheduling Research Involving Due Dates. OMEGA The Int. Jl. ofMgmt. Sci. Vol. 12, No.1, pp.63-76. Sidney, J.B., 1977. Optimal Single Machine Scheduling with Earliness and Tardiness Penalties. Operations Research, Vol.25, No.1, pp.62-69. Sundararaghavan, P.S. and M.U. Ahmed, 1984. Minimizing the Sum of Absolute Lateness in Single-Machine and Multimachine Scheduling. Naval Research Logistics Quarterly, Vol.31, pp.325-333. Townsend, W., 1978. The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution. Management Science, Vol.24, No.5, pp.530-534. Van Wassenhove, L.N. and L.F. Gelders, 1980. Solving a Bicriterion Scheduling Problem. European Journal of Operational Research, Vol.4, No.1, pp.42-48. Van Wassenhove, L.N. and K.R. Baker, 1982. A Bicriterion Approach to Time/Cost Trade-offs in Sequencing. European Journal of Operational Research, Vol.11, No.1, pp.48-54. 17

Table 1. Computational Results. (Machine load is ~.9) No. Heuristic Branch and Bound of Suo CPU CPU # of sub- min lower jobs Soluti time Solutio time problems bound 188.002 188 1.016 1653 112.002 112.089 92 225.003 225.786 1305 ____ 95.002 95.206 315 327.004 327** > 30. 16345 241 5 316.004 316** >30. 17238 241 220.004 220 31.876 t 30124 288.004 288.601 517 131.007 131** >30. 18657 120 110.006 110** > 30. 17099 76 110.006 110 5.438 4354 20 75.006 75** >30. 20075 55 69.006 69 2.313 1846 113.006 113** > 30. 15325 74 278.006 278** > 30. 16068 192 ____ 257.005 257 56.549 t 44417 209.010 209** > 30. 12584 63 3 174.010 174** > 30. 13134 122 30 732.012 732 ** > 30. 12396 289 386.011 386** >30. 10686 184 * CPU time in seconds on Amdahl 470V/8 system ** indicates that it is not verified as optimal ( it is current incumbent solution) t These problems were run for more than 30 seconds to get an optimal solution since the solution obtained after 30 seconds was very close to the lower bound.

Table 2. Computational Results. (Machine load is <.9) No. Heuristic Branch and Bound of,CPU CPU. #of sub- min lower jobs lution Solution probles bound time time problems bound 48.002 48.074 66 30.002 30.223 108 10 51.002 51.318 289 59.002 59.205 48 35.003 35.187 194 15 53***.003 51.590 473 18.005 18.554 437 188.005 188 37.826 t 30875 120.005 120.779 609 124 **.005 123.933 776 20 130.006 130 7.953 6139 99.005 99 4.906 3926 127.005 127 12.443 10223 354.006 354 ** > 30. 19330 269 61.009 61 2.819 1216 91.009 91 1.757 841 67.009 67 ** > 30. 13819 48 3 152.009 152 ** > 30. 13900 107 30 158.009 158 19.723 10060 121.009 121 8.911 4609 119.010 119 4.924 2108 303.010 303 ** > 30. 14590 188 100.015 100 ** > 30. 8610 47 216.015 216 ** > 30. 8654 176 40 659.016 659 ** > 30. 8105 225 471.016 471 ** > 30. 7510 192 * CPU time in seconds on Amdahl 470V/8 system ** indicates that it is not verified as optimal solution (current incumbent solution) *** indicates that it is not equal to optimal solution t This problem was run for more than 30 seconds to get an optimal solution.

N/M // (rTi+eiEi) I// S( TTi+ EiEi) N/1//T+E N/1/di=d/T+E Figure 1. Relationships among the problems

(Problem) (given sequence is 1,2,3,4,5,6) 1 2 3 5 6 3 4 (Algorithm) Visited Steps G =1 61 JOB 6 TG=1 Step 0 G. -1 d 5 5 JOB 5........ ~ _........................ '` ''.......... TG=0 Step 1 G =1 I G =1 _6 Move jobs 5 and 6 to right - JOB 4 G =1 3 - d 13 TG=2 Step 3 TG=1 Step 1 Step 3 TG=1 Step1 Step 2 TG=0 Step 1 TG=2 Step 3 JOB 3 FE 1% \ \% d 2 G =-1 2 a_ JOB 2 E d i 1% X %.e OF, I -- I % I t4O JOB 1 &~rr I., ~~ ~ ~~ Step 1 Step 3 - -. - MM W /// Step 4 Figure 2. An example for Algorithm 1.

d. I J d. I I i ----— '" ' ' ''''' ' ' " i............. - I.. ..... I...........-......... -......... -..-....:.......:,, ' '.,............. I i..''.......... I.. I.......:::.: -- - - - - - - - - - - - ~......~: ~.....:~~: ~... ~......~~ I I I.. ~~~ ~..:1,......~~~~ (ij) I m~ i ~:~.: ~~.: ~:. ~:. ~~:.:~::. '::: X.. -::- -:-::-:.:-:- -:-:,I...' '''............... '... - " ' '' ' ' (j,i):Better i i (a) d > d d. i I I d. ii = - - -- =I J..................................::: ':i~i:i I II:: I: ~:: i I I::-i-:l: —:-l:;~i_:~..........:-_:~ 1 J (i,j) Better Iee~ ~ r ~ rr kr Imi j I...................... ~... -. I.... I. I.:::, X:,.. ~ ~ ~ ~ - - (j,i) I i (b) d< d iI and pi +(d -di) > p j j (ij) Better i (iji) (c) d d,d i j pi +(d -d i) c p, and A<B A I d. d. 1I B I ~ ''I. - '...... I.... I.... ",;-... -............................. j I..............-............-..t -.............. I................ I I'.' - -.... " ' (i,j) I -I I Ifa,I 111 I I........... I........ I I.- I. - 11- -.11............. -... -. -.1..... 11.11-... I.-.., ''. I...... 1............. — - f I I (j,i): Better (d) d< d, I j Pi +(d dI) < pP, and A>B Figure 3. Pictorial view for Lemma 2. (Solid lines denote T+E )

2 1. (2,1) 1 [d1, d, (1,2): Better (a) max[C1, C 2] min ]: LPT d 1 d, - *A- -- -I - -- - (2,1): Better (1,2) 1 (b) min[s1, s2] 2 max[d1, d2]: SPT (2,1) (1,2) 1,d2]:SPT: Better 1 2 [p,p2] > max[d (c) min[s, s 2]+min Figure 4. Properties for pruning. (Lemma 5) (Solid lines denote T+E for 2 jobs. )

d d d d d 15 1 I z j, %.%l% %oll % %le.m % 2 3 -iJ~ ~ I-i i- lli _-"',"i~ i" - ~;,,:~.~,i- ~,'!! ~ ~ _ 7 ~_ _~ _ ~~~~~. _,_,.., __ 3~~~~~~~,.,..m ~f d 6 d 17 I I 4 21 t31 t41 32 to 7 t 33t24 23 t B2= (t21 + t + t23 +4 ) +2(t3+t32+t33 ) + 3 t41 Figure 5. Lower bound(B2) for T+E of the jobs in J\PS.