具有n个任务和m台机器的作业调度

Question

问题描述：

我有 n 个优先约束的作业和 m 台独立的机器。每个作业都分配有一个成本 c（在 1 个时间单位内完成作业所需的计算机数量）。完成一项作业需要 1 个时间单位，只有当 c 台机器分配给它时，作业才能完成（作业是原子的，不可能完成一半的作业）。

因此，简而言之，有n个作业及其优先级约束，m个机器和一个截止日期 >（一些时间单位）。

我的目标:

我想检查是否可以将作业分配给机器，以便所有作业都在 d 个时间单位内完成。如果这可能，那么我想打印出一个时间表，为每个作业分配一个时间单位（处理作业的时间单位，请参见下面的示例）。

例子：

n = 5; // number of jobs
m = 6; // number of machines
d = 4; // deadline (number of time units in which the jobs need to be finished)

Precedences: (read "Job(x,y)<--Job(q,p)" as "job x with cost y needs to be
              finished before job q with cost p can be started")
Job(3,1)<--Job(2,3)<--Job(1,4)
Job(5,3)<--Job(4,3)
Job(6,1)

 The solution: in this case it's possible to assign jobs to machines such that each job
finishes in <=d time units. 
A possible schedule is 1 2 3 3 4 1.

(read schedule as "job 1 and job 6 are done in the first time unit, job 2
is done during the second time unit, jobs 3 and 4 during the third time unit, 
job 5 during the fourth time unit")

我目前的方法：（第二次尝试感谢@Ole V.V.的反例）

我想做一个回溯的方法(我能想到的最好的方法)。目前我在实现它时遇到了麻烦。

我想存储作业及其优先级。然后我确定一个集合A，其中包含在当前时间单位内可以解决的所有作业。然后我找到一个集合B（它包含我认为在这个时间单位内解决的所有作业集），其中包含A的所有子集，这些子集可以用有限数量的机器m来解决，因此不能向每个子集添加其他作业（通过向其中一个子集添加作业，该子集中所有作业的成本超过'm'）。然后我重复该过程，但没有解决的作业（A\B），我对B中的每个子集进行递归调用。当传递的剩余作业集（A\B）为空（所有作业都完成）时，我停止，此时如果递归深度为

关于这种方法的例子由@Ole V.V .提供:

步骤指的是递归的深度，方框指的是作业（第一个数字是作业ID，第二个是时间单位成本。在步骤0，我明确地写出了子集（我在这一步骤中考虑解决的作业集）。

现在我的问题是存储作业及其优先级，找到可以在当前时间单位（集合A）中解决的作业，找到我认为在当前时间单位（集合B）中解决的作业子集，并将其全部放在一个递归函数中，最终输出找到的时间表或“找不到时间表”，如果没有满足最后期限的时间表。

Answer 1

你的方法似乎很好，但我相信有一种更简单的方法。我建议您使用约束saisfaction方法。有很多方法可以解决你的问题，例如混合整数编程，MaxSAT。你的任务似乎很简单，你肯定不会有太多的数字，所以你可以试试Minizin。例如，考虑这个调度示例。

如果我们在谈论特定于Java的工具，看看虫火谷解算器。

Answer 2

你所看到的问题显然是NP难的，我们可以从划分问题简化如下:假设你有一个整数s1，s2的划分问题...，sn。目标是找到这个集合的一个分划，分成两个集合S1和S2，使得S1上的和等于S2上的和。

我们可以通过为每个整数定义一个作业（其成本是整数的值）来将这个问题转换为您的问题，然后我们添加一个额外的作业，该作业必须在所有其他作业之后完成。我们设置d=3

我们可以很容易地证明，当且仅当您的问题有解决方案时，分区问题才有解决方案，因此您的问题是NP难的。

Answer 3

我相信你贪婪的算法不会总是给你正确的结果。

采取：

Job 1 costs 3
Job 2 costs 3
Job 3 costs 1
Job 4 costs 5
Job 5 costs 1

机器的数量是7。

优先顺序是

#1 before #5
#2 before #5
#4 before #3 before #5

截止日期是3点。

我相信你的算法会选择

Step 1 jobs 1, 2, total cost 6
Step 2 job 4 cost 5
Step 3 job 3 cost 1

现在作业 5 尚未运行，并且已到达截止日期。你的程序会说这是不可能的。

以下时间表是可能的

Step 1 job 4 cost 5
Step 2 jobs 1, 2, 3 total cost 7
Step 3 job 5 cost 1