Multiprocessor Scheduling Part 3

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

Không thể tạo bản xem trước, hãy bấm tải xuống
69    594    52
237    78    3    19-05-2024
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.