C语言中的抢占式任务调度

Question

我有一个任务列表，其中有3个参数需要考虑，同时调度:发布时间，持续时间和最后期限。

发布时间是任务的最早开始时间。工期是执行任务所需的时间。Deadline是任务的最新可能完成时间。

例如，输入是：

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

第一列为开始时间，第二列为结束时间，第三列为任务编号。

我认为我们需要用一个贪婪的算法来达到这个目的，但我不完全确定。

因此，我正在寻找解决这个问题的可能算法/方法。

Answer 1

在调度理论中，您的问题可以用以下符号表示：

1|r_j|sum(U_j)

(有关表示法的更多解释，您可以查看这个维基页面 )

根据本网站的说法，你的问题是NP难的，因为1|r_j|L_max是NP硬的.

这意味着您无法找到一种贪婪的算法来在多项式时间内解决您的问题(除非P=NP是一个o百万元的未决问题，但没有人真正相信它)。

Answer 2

我建议用精确方法的调度理论来解决这个问题。为您的问题编写一个数学模型将导致下面的最佳解决方案。

1 3 3

3 6 1

6 8 2

8 12 4

目标函数将延迟最小化，即迟到的天数。例如，有两天的时间晚了。