算法 - 最大限度地减少总的迟到

Question

我想实现一个精确的算法，尽量减少单机的总拖期。我在网上搜索了解如何使用动态编程实现它。我阅读了Lawler的论文，他在77年提出了PSEUDOPOLYNOMIAL算法。但是，仍然无法将其映射到java或c＃代码中。

请你帮我提供一些参考如何有效地实现这个确切的算法？

编辑1：@bcat：不是真的。我需要为我们的软件实施它。 :(还是我无法找到任何指导如何实现它。贪婪的一个很容易实现，但调度的结果并不令人印象深刻。

亲切的问候，

Xiaon

Answer 1

也许石溪算法库的Job Scheduling Section可以帮助你。

Answer 2

你可以有不同的变量的数值范围和输入的整体特性一起指定您的特定问题的确切特性。

如果没有此设置，我假设您使用此定义：

您希望将具有n个独立作业（每个作业都有其处理时间和到期日期）的单个机器调度问题的总时间最小化。

你想要做的是挑选一部分作业，使它们不重叠（单机可用），你也可以选择你做的顺序，保持截止日期。

我想要做的第一步是按截止日期进行排序，似乎没有以某种不同的方式对它们进行排序的好处。

下一步剩下的是挑选子集。这是动态编程帮助的地方。我将尝试描述状态和递归关系。

国家：

[current time][current job] = maximum number of jobs done 

关系：

你要么处理当前工作，并呼吁

f(current time + processing_time_of[current job],current job +1) 

，或者你跳过过程，并呼吁

f(current time,current job +1) 

最后你花最少的那些调用返回的2个的值，并将其存储在状态

[current time][current job] 

你在时间0和作业0开始递归。

顺便说一句，贪婪似乎做得相当好，检查了这一点：

http://www.springerlink.com/content/f780526553631475/

Answer 3

对于单机，处理时间最长的时间表（也称为减少时间的算法），如果你是最佳提前知道所有的工作，并且可以将他们从最长到最短（所以你需要做的就是排序）。

如前所述，您没有指定有关您的日程安排问题的信息，因此除此之外很难提供帮助（因为没有普遍优化的和高效的调度程序存在）。