活动或任务计划问题

这是在单个处理器上最佳安排单位时间任务的争议, 其中每个作业都有最后期限, 如果错过了最后期限, 则必须支付罚款。

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

为每个处理器安排带有期限和罚款的单位时间任务的争议有以​​下输入：

• n个单位时间任务的集合S = {1, 2, 3 ….. n}。
• 一组n个整数截止期限d1 d2 d3 … dn, 使得di满足1≤di≤n, 并且任务i应该在时间di之前完成
• 一组n个非负权重或罚分w1 w2 …. wn, 这样, 如果任务i在时间di之前未完成, 我们将受到wi的惩罚, 而如果任务在其截止日期之前完成, 我们将不会受到惩罚。

在这里, 我们找到了S的时间表, 该时间表可最大程度地减少因错过截止日期而产生的总罚款。

如果任务在截止日期之后完成, 则它在此计划中延迟。否则, 任务将排在计划的早期。可以将任意计划始终以早期优先的形式放置, 在该形式中, 第一个任务优先于后一个任务, 即, 如果某个新任务x在某个后任务y之后, 则我们可以切换x和y的位置而不会影响x被早或晚。

总是可以将任意计划安排成规范的形式, 在该形式中, 第一个任务优先于后一个任务, 并且第一个任务按截止日期的顺序递减。

如果存在特定任务的计划, 则任务A的任务是独立的, 这样就不会延迟任务。因此, 计划的第一组任务形成一个独立的任务集“ l”, 表示所有独立的任务集。

对于任何任务集A, 如果t = 0、1、2 ….. n, 则A是独立的, 我们有Nt（A）≤t, 其中Nt（A）表示A的任务数为t或优先, 即如果预期A中的任务按截止时间单调增长的顺序进行, 则没有任务迟到。

示例：在给定的权重（罚款）和截止日期下, 找到以下任务的最佳计划。

解决方案：根据Greedy算法, 我们以罚款的降序对作业进行排序, 以便收取最低的罚款。

在此问题中, 我们可以看到单处理器计算机将以6个单位运行的最大时间, 因为这是最大期限。

令Ti代表i = 1至7的任务

T7之后不能接受T5和T6, 因此罚款

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）是最佳的。