Tham khảo tài liệu 'multiprocessor scheduling part 5', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 110 Multiprocessor Scheduling Theory and Applications Tịi i 1 2 m R 7ỉ n m R C L . For the total idle time U L the next lemma provides an upper bound. Lemma 6. For any job list L J1 J2 . Jn we have m LTJ m-L J mCmaĩ L m0 m Proof. By the definition of R no machine has idle time later than time point R. We will prove this lemma according to two cases. Case 1. At most machines in A are idle simultaneously in any interval a b with y I -l a b. . Let vi be the sum of the idle time on machine Mi before time point and be the sum of the idle time on machine Mi after time point i 1 2 . m. The following facts are obvious Uị L Vi Vị Vị 0 Vi A. Ỉ i m In addition we have Ư ieA because at most m- LtJ machines in A are idle simultaneously in any interval a b with a b R. Thus we have U L Ui L mC L z. y y Ềí mCOPT L 2 mCOPT L - èí rnCOPT L ị C L . m-L J l-J C T L - 2 mRCOPT mCOfJ L LtJ m - LTJ mf3 m On-line Scheduling on Identical Machines for Jobs with Arbitrary Release Times 111 Case 2. At least . machines in A are idle simultaneously in an interval a b with a b. In this case we select a and b such that at most m - LiJ machines in A are idle simultaneously in any interval a1 b1 with a b 1 a1 b . Let A i G is idle in a 6 . That means . by our assumption. Let I be such a machine that its idle interval a b is created last among all machines . i . I. Let 4 4 i0 . Suppose the idle interval a b on machine is created by job - . That means that the idle interval a b on machine Mi for any t - A1 has been created before job - is assigned. Hence we have - for any i--A . In the following let r-ki min rĩo min rĩi ie-4 . We have b because . A b and Ab it - A1. What we do in estimating is to find a job index set S such that each job Jj j - S satisfies . and 11 . . And hence by 8 we have rOPT To do so we first show that n r7 J- 9 holds. Note that job must be assigned in Step 5 because it is an idle job. We can conclude that 9 holds if we can prove that job is assigned in Step 5 because the .