演算法›Ch7 貪婪演算法
第 6 題/共 12 題
◀ AL 6/12
6. Weighted Completion Time、Smith's Rule、Greedy
#AL-07-006中Weighted Completion TimeSmith's RuleGreedy

Assuming that the available time for the classroom is unlimited, we instead focus on the course completion time. We aim to schedule nn courses, where each course ii is characterized by its duration pip_i and weight wiw_i. In this schedule, the finish time of each course is the total duration of all courses scheduled before it, plus its duration. A schedule can be defined as a function d(i)d(i), representing the order of course ii in the schedule. That is, if d(i)<d(j)d(i) < d(j), course ii is scheduled before course jj. Therefore, the finish time of course ii is denoted as fi=∑j∈{1,…,n}: d(j)<d(i)pjf_i = \sum_{j \in \{1,\ldots,n\}:\, d(j) < d(i)} p_j. This scheduling problem aims to minimize the total weighted finish time ∑i∈{1,…,n}wifi\sum_{i \in \{1,\ldots,n\}} w_i f_i. Suppose we have 15 courses with corresponding durations [6, 6, 9, 83, 34, 44, 164, 38, 82, 180, 19, 128, 394, 512, 15] and weights [2, 4, 4, 6, 7, 7, 7, 10, 10, 10, 11, 12, 13, 13, 15]. What is the value of the optimal schedule, that is, the minimum total weighted finish time?

📄 成大114
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch7 貪婪演算法
本章題號 · 1–12 / 12