04greedy算法设计与分析 贪心算法(16)

Scheduling to Minimizing LatenessMinimizing lateness problem. Single resource processes one job at a time. Job j requires tj units of processing time and is due at time dj. If j starts at time sj, it finishes at time fj = sj + tj. Lateness: j = max { 0, fj - dj }. Goal: schedule all jobs to minimize maximum lateness L = max j.

Ex:

1 tj dj 3 6

2 2 8

3 1 9

4 4 9

5 3 14

6 2 15

lateness = 2

lateness = 0

max lateness = 6

d3 = 90 1

d2 = 82 3

d6 = 154 5 6

d1 = 67 8

d5 = 149 10 11 12

d4 = 913 14 15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库04greedy算法设计与分析 贪心算法(16)在线全文阅读。