# 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

TÀI LIỆU LIÊN QUAN
81    833    54
130    465    7
27    206    2
30    164    2
36    289    11
124    340    9
30    176    3
68    24    2
112    495    27
69    594    52
TÀI LIỆU XEM NHIỀU
13    40790    2406
3    24898    248
25    24388    4276
16    19994    2843
20    19448    1542
14    19218    2965
1    19205    614
37    16109    2958
3    15884    328
1    14515    132
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
68    245    3    19-05-2024
7    72    1    19-05-2024
25    79    1    19-05-2024
225    187    3    19-05-2024
14    256    1    19-05-2024
10    286    2    19-05-2024
237    78    3    19-05-2024
5    329    1    19-05-2024
10    79    1    19-05-2024
5    80    2    19-05-2024
41    96    2    19-05-2024
50    86    8    19-05-2024
7    384    2    19-05-2024
5    82    2    19-05-2024
94    71    1    19-05-2024
36    867    10    19-05-2024
32    99    1    19-05-2024
134    60    2    19-05-2024
3    75    3    19-05-2024
7    200    1    19-05-2024
TÀI LIỆU HOT
3    24898    248
13    40790    2406
3    2744    81
580    5038    363
584    3313    100
62    6632    1
171    5675    719
2    3101    78
51    4419    200
53    4708    188
Đã 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.