P | prmp | Cmax (Cj is minimum) can be solved in polynomial time. O(n log n ) time J. Leung and G. Young, Minimizing Schedule Length Subject to Minimun Flow Time, SIAM J. on Computing, 18:314-326, 1989 1. Assume n is a multiple of m. Otherwise, introduce dummy jobs with zero processing times. 2. Sort the jobs in ascending order of processing times. 3. Schedule the first n-m jobs by strict SPT mode. 4. Compute OFT as follows. Assume f1 f2 . . . . fm, where fi is the finishing time of machine i (i) f1 + Pn (ii) (f1 + f2 + Pn + Pn-1) (iii) 1/3 (f1 + f2 + f3 + Pn + Pn-1 + Pn-2) . . . (m) 1/m (f1 + f2 + . . . + fm + Pn + Pn-1 + . . . + Pn-m+1) OFT is the maximum of the above m quantities. f1 f2 f3 OFT fm-1 fm CS 537 Scheduling Algorithms 46 5. Schedule the jobs n, n-1, n-2, . . . . ., n-m+1, in that order as follows. Rule 1: If the job can fit completely in the machine with least capacity, then schedule the job into the machine and delete the machine from consideration. Rule 2: If the job can fit perfectly into one machine without any idle time, then schedule the job on that machine and delete the machine from consideration. else Rule 3: There must be an index i such that (OFT fi) > Pj and (OFT fi+1) Use Leung-Young algorithm to construct a preemptive schedule for the following jobs on 4 identical and parallel machines. Use Leung-Young algorithm to construct a preemptive schedule for the following jobs on 4 identical and parallel machines