C中的抢占式任务调度
Preemptive task scheduling in C
我有一个任务列表，其中有 3 个参数在安排时要考虑：发布时间、持续时间和截止日期。
释放时间是任务的最早可能开始时间。 Duration 是执行任务所花费的时间。 截止日期 是任务的最晚可能完成时间。
例如输入为：
4
2 3 5
4 2 8
1 2 6
6 4 11
这意味着有 4 个任务，如第一行所示。从下一行开始，第一列是发布时间，第二列是持续时间，第三列是每个任务的截止日期。
安排这些任务的方式是：
Time Task
1-2 3
2-5 1
5-6 3
6-8 2
8-12 4 <--- Deadline Violation
目标是编写一个算法来安排任务，从而最大限度地减少违反截止日期的次数。
因此，对于上述情况，我们必须有一个输出：
1 2 3
2 5 1
5 6 3
6 8 2
8 12 4
其中第一列是开始时间，第二列是结束时间，第三列是任务编号。
我认为我们需要为此目的使用贪心算法，但我不完全确定。
因此，我正在寻找可能的 algorithms/approaches 来解决这个问题。
在调度理论中，您的问题可以用以下符号表示：
1|r_j|sum(U_j)
（您可以查看 this wikipage 以获得更多关于符号的解释）
根据this website，
你的问题是 NP-hard 因为例如 1|r_j|L_max 是 NP-hard.
意思是你找不到一个贪心算法可以在多项式时间内解决你的问题（除非P=NP，是一个one-million dollar open question，但是没有人真正相信它）。
我建议通过关于精确方法的调度理论来解决这个问题。为您的问题编写数学模型会得出以下最优解。
1 3 3
3 6 1
6 8 2
8 12 4
objective 函数最大限度地减少了迟到，即 "days" 迟到的次数。例如，你迟到了 2 天。
我有一个任务列表，其中有 3 个参数在安排时要考虑：发布时间、持续时间和截止日期。
释放时间是任务的最早可能开始时间。 Duration 是执行任务所花费的时间。 截止日期 是任务的最晚可能完成时间。
例如输入为：
4
2 3 5
4 2 8
1 2 6
6 4 11
这意味着有 4 个任务，如第一行所示。从下一行开始，第一列是发布时间，第二列是持续时间，第三列是每个任务的截止日期。
安排这些任务的方式是：
Time Task
1-2 3
2-5 1
5-6 3
6-8 2
8-12 4 <--- Deadline Violation
目标是编写一个算法来安排任务，从而最大限度地减少违反截止日期的次数。
因此，对于上述情况，我们必须有一个输出：
1 2 3
2 5 1
5 6 3
6 8 2
8 12 4
其中第一列是开始时间，第二列是结束时间，第三列是任务编号。
我认为我们需要为此目的使用贪心算法，但我不完全确定。
因此，我正在寻找可能的 algorithms/approaches 来解决这个问题。
在调度理论中，您的问题可以用以下符号表示：
1|r_j|sum(U_j)
（您可以查看 this wikipage 以获得更多关于符号的解释）
根据this website， 你的问题是 NP-hard 因为例如 1|r_j|L_max 是 NP-hard.
意思是你找不到一个贪心算法可以在多项式时间内解决你的问题（除非P=NP，是一个one-million dollar open question，但是没有人真正相信它）。
我建议通过关于精确方法的调度理论来解决这个问题。为您的问题编写数学模型会得出以下最优解。
1 3 3
3 6 1
6 8 2
8 12 4
objective 函数最大限度地减少了迟到，即 "days" 迟到的次数。例如，你迟到了 2 天。