Division of Research Graduate School of Business Administration The University of Michigan BOUNDS FOR EARLINESS PROBLEMS Working Paper No. 425 Ram Mohan V. Rachamadugu April 1985 FOR DISCUSSION None of this material reproduced without the of the Divisior PURPOSES ONLY L is to be quoted or i expressed permission i of Research. I

Bounds for Earliness Problems Introduction Most prior research in scheduling has largely been confined to various measures of performance which are regular. For a detailed definition of regular measures of performance see Baker [1974]. However, with the increasing emphasis and popularity of 'Pull' type systems (Just-in-Time is a special type of Pull type systems), there is need to look into other performance measures which are relevant to such systems. One such measure is earliness of a job. Earliness of a job i is denoted as follows: ei = max(0, di-ci) where d. is the due date of job i and c. is the completion time of job i. One major objective in practice is to schedule jobs in such a way that no job is tardy and at the same time we wish to minimize the total earliness of the jobs. If jobs are significantly different from each other, then we can further generalize the above criterion as weighted earliness problem. wei = wimax(O, di-c ) where w. = penalty factor for job i. In this case, we want to schedule jobs in in such a way that the sum of weighted earliness is minimized subject to the condition that no job is tardy. In this paper, we analyze the bounds and properties of earliness and weighted earliness problems in the context of single machine scheduling. It may be noted that both are non-regular measures of performance. Thus mere investigation of permutation schedules is not necessarily sufficient to find optimal solutions. Investigation into problems of this nature has been done by various researchers. Ow [1984] recently investigated a more general criterion where jobs are subject to both earliness and lateness penalties. However, she studied problems where no inserted idle time was permitted. Chand and

-2 - Schneeberger [1984] investigated weighted earliness problem and developed heuristics and a dynamic programming based optimum seeking procedure. The purpose of this paper is to develop procedures for determining lower bounds for these problems which are easy to compute. Secondly, we develop performance bounds for the heuristic developed by Chand and Schneeberger [1984] when it is applied to earliness problems. Formally, the problem can be stated as follows: min Z Wi(d -c) P1 s.t c. < d 1- i Relaxation One of the ways in which one can find lower bounds is to relax some or all of the contraints and then solve the problem. A popular method for such relaxation is Lagrangian relaxation. For a detailed description of Lagrangian relaxation procedures see the studies by Fisher [1981] and Geoffrion [1974]. Potts and Van Wasserhoven [1983] derived a procedure based on primal heuristics for finding Lagrangian duals which provide bounds for the problem. In our case, we consider an alternate relaxation of the problem. Further, we show that the optimum solution to the relaxation proposed by us is superior to the bound provided by primal-heuristic based dual procedure. Proposition 1: Consider any job Jk. Suppose that Jk is split into two jobs — the first job J' with processing time P', due date dk and weight -Wk p and second jight j2 second job J2 with processing time ( -Pk'), due date (dk-pk) and weight k Pk k' Wk(I- kP ). Optimum solution to this relaxed problem is a valid bound on the original problem. Proof: Consider any feasible sequence to the original problem. We note that with appropriate notational change, any feasible sequence to the original problem is also a feasible sequence to the relaxed problem. Suppose Jk

-3 - completes at time ck in a feasible sequence to the original problem. J2 J ck- Pk ck contribution of Jk to the objective function = wk(dk-ck) contribution of the same sequence to the relaxed problem k (P)(dk-ck) + ( 1 - )(dk-k-(ck-p )) = k(d-) Pk k k-k Pkk kkk k kkk Therefore, optimal solution to the relaxed problem is a valid bound for the original problem. Remark 1: Optimal solution to the relaxed problem obtained by splitting jobs into more than two pieces is a valid bound on the original problem. Proof: Proof is by induction using proposition 1. Chand and Schneeberger [1984] suggested the use of Modified-Smith heuristic for the weighted earliness problem. Further, they suggest the use of dynamic programming for finding optimal solution to this problem. However, the limitation of this approach is the curse of dimensionality —requirements of statespace considerations which limit the use of procedures to small problems. They could use their procedure for solving problems upto 10 jobs. Dual based lower bounds We can determine a lower bound on the weighted earliness problem using the approach suggested by Potts and Van Wasserhoven [1983]. Chand and Schneeberger [1984] have shown that the sequence generated by Modified-Smith heuristic is optimal if jobs within each production block are in decreasing order. We may rewrite P1 as follows:

-4 - max Zwici P2 s't c. < d. 1 - 1 Lagrangian relaxation for P2 may be written as min max Ewic + Xi(d -c) Xi i ii i l min max S(w -Xi)c. + Xdi Xi ci 1 iL i xi ci For any given feasible c. values, z(X) is minimized if jobs are in decreasing order of within each production block. Since ciis can be comorder of wi-_i within each production block. Since ci < di, Wi-Xis can be computed as follows: Consider any two adjacent jobs J and J. in the sequence J Ji. J Pi Pj wi-Xi <w._X, > J X. w w -X. Pi -Pi P Since X. > 0, w. X Xi = max{0, wi - pit - — 1) } p P It may be noted that in each production block, last job completes on time and its X = O. X values can be earily found starting from the last job in the sequence generated by Modified-Smith heuristic. Let us call this bond B1. Bound based on pre-emption It may be noted that in the above lower bounding scheme, all X = 0 if jobs are in natural decreasing order in each block. Bound based on pre-emption is as follows: Let Ji and J. be last pair of adjacent jobs in the sequence obtained by using Modified-Smith heuristic such Pi P I j that J. immediately precedes J. and - < -. Note that X. =0.

-5 - e Ji I.i J d. T d. 1 J Also, let J immediately precede Ji. From the construction, it is obvious that that T - p. < d. < T < d Now consider splitting Jj into two piecesW. Piece 1 - J! with processing time (T-d ) weight - (T-di ) and due date d.. i i iF (T-di) 2 W. Piece 2 - J. with processing time (pj - (T-di)), weight p3 (p - (T-dj) and due date (dj - (T-di)). Now consider the following sequenceJe J Ji J T T-p.-p. d. T '1 -J 1 sequence same as before. Ji completes on time. Therefore, Xi = 0. = i Since >, 2. w. w. W. j j i i -----— > sequence same as before. X2 =0. i From the original sequence, w - X wi- x w. e e < i < Pj Pe Pi - Pi 1 From the new sequence, w - new. e P - Pi 2

-6 - From 1, w w. X X > p { - } + 3 e- e Pe Pi e Pi From 2, w W. X new > p {I e _ } 4 e - e Pe Pi comparing 3 and 4, Xe 2> enew Now consider the contribution made by Ji and Jj to the objective function value Contribution in the previous scheme = w T + wi(T-pj) + Xi(di - (T-pj)) 5 Let T-di = k. Contribution in the revised scheme w. w. = (T-di)T + wid + - (pj-(T-d ))(d -pi) pi i p j i J j w w = - (k)T + w + (pj-k) (di-Pi) _-6 5 can be rewritten as w.T + wi(T-pj) + Xi(pj-k) 7 J 1 J 1J 7 -6 equals = wT - kT - - (pj-k)(di-Pi) + wi(T-Pj) - w.d + Xi(Pj-k) =wj P Tp -kT-(p.-k)(d -Pi) + wi(T-p -d.) + X j(p.-k) p. J 3 i w W= j (pj-k)(T-di+Pi) + wi(-pj+k) + Xi(Pj-k) = (pj-k) -p (T-di+pi) - w. + X Pi w=(p -k) p (k+Pi) - (i + Xi) Pj - k wj wi - Xi k + Pi P k - Pi 1j 3:P

-7 - We note that pj-k and k+Pi are positive. Also, we know our earlier (wi-Xi) wj analysis that p < J. Since k is also positive, 7-6 > 0. i j Since X > new and also 7 - 6 > 0, the bound obtained with pre-emption of J. e- e - is tighter than B1. Rest of the proof is by induction. We can further improve the bounds by job splitting other jobs. Thus X = 0 for all jobs when job splitting is done. It appears that the bounds obtained using preemption perform quite well. In studies by Ow [1984], pre-emptive bounds provided tight lower bounds for early/tardy problems. Note that we are permitted to split jobs as often as necessary. Since due date and processing time information is in integers, value of the solution obtained using pre-emption is same as the value of the solution obtained using assignment procedure with jobs being split into lengths of unit processing time. Applications to average earliness problem Consider a special case of the above problem when all jobs are equally important - i.e., w. = 1 for all jobs. In this situation, we can get optimal solutions under certain special circumstances. Proposition 2: If jobs have agreeable due dates, then Minimum Slack Time Rule yields optimal premutation of jobs. (Jobs are considered to have agreeable due dates if di < dj ==> Pi > Pj for all combinations i and j.) Proof: If p. > p ==> R. > R. (in the parlance of Chand and Schneeberger -- J 1 - [1984]) d < dj, P > j ==> d i - d - p j Thus, Minimum Slack Rule yields optimal permutation of jobs. Exact start times of jobs can easily be derived once the sequence in known.

-8 - It may also be noted that application of Modified-Smith Rule is same as minimum slack time rule in this special case of the problem. Proposition 3: If the problem is feasible, there earliest due date rule yields minimum job earliness among all permutation schedules. Proof: Firstly, it may be noted that this is not a regular measure of performance. Hence we confine our attention to permutation schedules. It is well known that earliest due date rule minimizes L [Baker 74]. max minimize L = min max (c -d.) max i i = min min (d -c ) i i Performance bound In this section, we establish performance bound for Modified-Smith heuristic in the case of average earliness problem. The criterion we use is as follows: Heuristic value - Optimum value Number of jobs A more conventional performance measure which is used is as follows: Heuristic value - Optimum value M2 Optimum value Though M2 is more widely used, we prefer M1 since even a 'good' heuristic can appear to be 'bad' when M2 is used in problems such as the one we are considering. This is particularly true when optimum values are positive and near zero. Measure Ml measures absolute value of the deviation per job, thus explicitly taking into consideration at least one experimental factor. Proposition 4: Performance of Smith heuristic for average earliness problem is bounded by

-9 - (np -Pmin) (- p - ) max where p is average processing time of the jobs. Proof: Consider the Lagrangian relaxation of Smith heuristic for earliness problems. where c. is the comple that L(X) is a bound c Heuristic - optin solution solut < E(d Let L(X) = 2 (1- i)(di-ci) ition time using Smith heuristic. Further, a )n optimum solution. ial < Heuristic - Lagrangian based on;ion solution optimal solution -c ) - Z(1-X )(d.-c.) < EX(d -ci) 1 i 1 1 1 1 1 we know It can easily be verified that X < ( 1-i- ). Therefore RHS can be ~ Pmax written as Z(1- P ) (di-ci) max The above can be rewritten as p. (di-Ci)max i p ma =L P max In the worst case (d -ci) = makespan - p (i i max min Smith heuristic is guaranteed as follows: Hence, performance of Smith heuristic - optimal value <1 (n Pi n -n min i Pma < (np- pin) (1 - ). max Conclusion In this paper, we analyzed a non regular measure of performance which appears to be of importance in 'Pull' type of producton systems. Further, we derived the lower bounds for the performance of heuristic procedures for

-10 - these problems. Enumerative procedures are likely to be of extremely limited use in developing and validating new procedures for these problems. Development of good lower bounds will help in validating new heuristics for there problems. We have shown that lower bounds developed through pre-emption provide better bounds than primal heuristic based Lagrangian relaxation. Further, we derived performance guarantee for the modified form of Smith heuristic. The procedures developed by us can be integrated into more complex situations. Modified-Smith heuristic can very easily be extended to identical parallel machines. Similarly a lower bound using pre-emptive procedure can be obtained in this case also. Extensions are flow-shops and job shops are currently being explored. References Baker, K. R. 1974. Introduction to Sequencing and Scheduling, John Wiley and Sons, Inc. Ow, P. S. 1984. Heuristic Knowledge and Search for Scheduling, Ph.D. Thesis, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh. Chand, S. and Schneeberger, H. 1984. Single Machine Scheduling to minimize Weighted Earliness Subject to no job tardy, Krannert Graduate School of Management, Purdue University. Fisher, M. L. 1981. Lagrangian Relaxation Method for Solving Integer Programming Problems, Management Science, Vol. 27, No. 1, p. 1-18. Potts, C. N. and Van Wassenhoven, L. N. 1983. An Algorithm for Single Machine Sequencing with Deadlines to Minimize Total Weighted Completion Time. European Journal of Operations Research, Vol. 12, pp. 379-387.