活动或任务调度问题

这是关于在单个处理器上最优地调度单位时间任务的争论，其中每个作业都有一个截止日期，如果错过了截止日期，则必须支付罚款。

单位时间任务是一个作业，例如要在计算机上运行的程序，需要恰好一个时间单位才能完成。给定有限的任务集合 S，S 的调度是 S 的一个排列，指定了执行这些任务的顺序。调度中的第一个任务在时间 0 开始并在时间 1 结束；第二个任务在时间 1 开始并在时间 2 结束，依此类推。

对于每个处理器，调度具有截止日期和惩罚的单位时间任务的争论具有以下输入

• n 个单位时间任务的集合 S = {1, 2, 3.....n}。
• n 个整数截止日期 d₁ d₂ d₃...d_n 的集合，使得 d_i 满足 1≤ d_i ≤ n 并且任务 i 应该在时间 d_i 之前完成，并且
• n 个非负权重或惩罚 w₁ w₂....w_n 的集合，如果我们没有在时间 d_i 之前完成任务 i，我们将承担 w_i 的惩罚，并且如果任务在其截止日期之前完成，我们将不承担任何惩罚。

在这里，我们找到一个 S 的调度，该调度使错过截止日期的总惩罚最小化。

如果任务在此调度中在其截止日期之后完成，则该任务是 迟到的 。 否则，任务在调度中是提前的。 任意调度可以始终放入 提前优先形式，其中提前的任务优先于迟到的任务，即，如果某个新任务 x 跟随某个迟到的任务 y，那么我们可以切换 x 和 y 的位置，而不会影响 x 提前或 y 迟到。

任意调度始终可以放入 规范形式，其中提前的任务优先于迟到的任务，并且提前的任务按照非递减的截止日期顺序进行调度。

如果存在特定任务的调度，使得没有任务迟到，则任务集合 A 是 独立的 。 因此，调度的提前任务集合形成一个独立的任务集合，'l' 表示所有独立的任务集合的集合。

对于任何任务集合 A，如果对于 t = 0, 1, 2.....n，我们有 N_t(A) ≤ t，则 A 是独立的，其中 N_t(A) 表示 A 中截止日期为 t 或之前的任务数量，即如果 A 中的任务按照单调递增的截止日期顺序排列，则没有任务会迟到。

示例： 找到以下任务的最佳调度方案，并给出权重（惩罚）和截止日期。

解决方案： 根据贪婪算法，我们按照惩罚递减的顺序对作业进行排序，以便收取最低的惩罚。

在这个问题中，我们可以看到单处理器机器运行的最长时间为 6 个单位，因为它是最大截止日期。

令 T_i 表示任务，其中 i = 1 到 7

T₅ 和 T₆ 不能在 T₇ 之后接受，所以惩罚是

w5 + w6 = 30 + 20 = 50 (2 3 4 1 7 5 6)

另一个调度是

(2 4 1 3 7 5 6)

可以有很多其他调度，但（2 4 1 3 7 5 6）是最优的。