Tham khảo tài liệu 'multiprocessor scheduling part 3', 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ả | 50 Multiprocessor Scheduling Theory and Applications WSPT schedule Figure 1. Illustration of the rules WSPT and WSRPT From Theorem 4 we can show the following proposition. Proposition 1 26 16 Let g 1 n -1- _ i l i 7 2 The quantity b is a lower bound on the optimal weighted flow-time for problem1 . Theorem 5 Kacem Chu and Souissi 12 Let . . y ir ợ y tr Ợ A7-I yy ip I hl 7 . 1 i g 2 p j x The quantity lb2 is a lower bound on the optimal weighted flow-time for problem and it dominates lb1. Theorem 6 Kacem and Chu 13 For every instance of the lower bound lb2 is greater than lb0 lb0 denotes the weighted flow-time value obtained by solving the relaxation of the linear model by assuming that Xi G 0 1 . In order to improve the lower bound lb2 Kacem and Chu proposed to use the fact that job . must be scheduled before or after the non-availability interval . either i . or Í must hold . By applying a clever lagrangian relaxation a stronger lower bound lb3 has been proposed Theorem 7 Kacem and Chu 13 Let 8 _ Í Ws 1 - 5 2 exists with L Wg 1 otherwise and . Scheduling under Unavailability Constraints to Minimize Flow-time Criteria 51 The quantity lb3 is a lower bound on the optimal weighted flow-time for problem Ì and it dominates lb2. Another possible improvement can be carried out using the splitting principle introduced by Belouadah et al. 2 and used by other authors 27 for solving flow-time minimization problems . The splitting consists in subdividing jobs into pieces so that the new problem can be solved exactly. Therefore one divide every job i into Hi pieces such that each piece i k has a processing time T and a weight Ụ V1 k ni with and Efc iWi- Using the splitting principle Kacem and Chu established the following theorem. Theorem 8 Kacem and Chu 13 Index Z1 denotes the job such that . and m . . and index z2 denotes the job such that and . j . We also define . f j and . _ . Therefore the quantity lb4 min p y2 is a lower bound on the optimal weighted flow-time for and
