具有可变资源的调度

Question

(首先，对不起我的英语，它不是我的第一语言)

我有一个任务/作业列表，每个任务必须在特定的开始时间之后开始，需要运行一定的时间，并且必须在特定的结束时间之后完成。

我可以动态地添加和删除工作进程，因此如果有必要的话，可以同时执行2个或更多任务。我的目标是找到一个调度计划，它能成功地执行每个作业，并尽可能使用最少的工人。

我目前正在使用EDF (http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling)算法，如果它不能正确地调度所有作业，则递归地调用具有更高工作者限制的函数，但我认为这不能正常工作，因为我没有真正的方法来衡量何时可以再次降低资源限制。

有没有什么算法可以解决我的问题，或者有什么其他聪明的想法？

谢谢你的帮助。

Answer 1

调度问题通常可以通过将其表示为混合整数规划(MIP)来非常有效地解决

http://en.wikipedia.org/wiki/Mixed_integer_programming#Integer_unknowns

或者使用约束编程(CP)来表达它

http://en.wikipedia.org/wiki/Constraint_programming

对于MIP或CP，您将找到可以解决您的问题的免费和商业解决方案。

在这两种方法中，您都将精力放在说明解决方案必须具有的属性上，而将应用适当算法的艰苦工作留给专门的求解器。