算法——最小化总迟到率
我正在尝试实现一种精确的算法来最小化单台机器的总迟到率。我在网上搜索以了解如何使用动态编程来实现它。我读了 Lawler 的论文，他在 77 年提出了伪多项式算法。但是，仍然无法将其映射到 java 或 c# 代码中。
您能帮我提供一些如何有效实现这个精确算法的参考吗？
Edit-1：@bcat：不是真的。我需要为我们的软件实现它。 :( 我仍然找不到任何如何实现它的指导。贪婪的很容易实现，但调度的结果并不那么令人印象深刻。
亲切的问候，
Xiaon
I am trying to implement an exact algorithm of minimizing total tardiness for single machine. I was searching in the web to get an idea how I can implement it using dynamic programming. I read the paper of Lawler who proposed a PSEUDOPOLYNOMIAL algorithm back in 77. However, still could not able to map it in java or c# code.
Could you please help me providing some reference how to implement this exact algorithm effectively?
Edit-1: @bcat: not really. I need to implement it for our software. :( still I am not able to find any guidance how to implement it. Greedy one is easy to implement , but result of scheduling is not that impressive.
Kind Regards,
Xiaon
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以指定特定问题的确切特征以及不同变量的限制和输入的总体特征。
如果没有这个，我假设您使用这个定义：
您希望最大限度地减少具有 n 个独立作业的单机调度问题中的总延迟，每个作业都有其处理时间和到期日期。
您想要做的是选择作业的子集，以便它们不会重叠（单台机器可用），并且您还可以选择执行这些作业的顺序，并保留截止日期。
我想要做的第一步是按截止日期排序，似乎以某种不同的方式对它们进行排序没有任何好处。
接下来剩下的就是选择子集。这就是动态规划可以发挥作用的地方。我将尝试描述状态和递归关系。
状态：
关系：
您要么处理当前作业并调用
，要么跳过该过程并调用，
最后您取这些调用返回的 2 个值中的最小值并将其存储在state
你在时间 0 和作业 0 开始递归。
顺便说一句，贪婪似乎做得很好，看看这个：
http://www.springerlink.com/content/f780526553631475/
You could have specified the exact characteristics of your particular problem along with limits for different variables and the overall characteristics of the input.
Without this, I assume you use this definition:
You want to minimize the total tardiness in a single machine scheduling problem with n independent jobs, each having its processing time and due date.
What you want to do is to pick up a subset of the jobs so that they do not overlap (single machine available) and you can also pick the order in which you do them, keeping the due dates.
I guess the first step to do is to sort by the due dates, it seems that there is no benefit of sorting them in some different way.
Next what is left is to pick the subset. Here is where the dynamic programming comes to help. I'll try to describe the state and recursive relation.
State:
Relation:
You either process the current job and call
or you skip the process and call
finally you take the minimum of those 2 values returned by those calls and store it in state
And you start the recursion at time 0 and job 0.
By the way, greedy seems to be doing pretty well, check this out:
http://www.springerlink.com/content/f780526553631475/
对于单机来说，如果您提前知道所有作业并且可以将它们从最长到最短排序（因此您所需要做的就是排序），则最长处理时间计划（也称为递减时间算法）是最佳选择。
正如已经提到的，您没有指定有关调度问题的任何信息，因此很难提供除此之外的帮助（因为不存在普遍最佳的和高效调度程序）。
For single machine, Longest Processing Time schedule (also known as Decreasing-Time Algorithm) is optimal if you know all jobs ahead of time and can sort them from longest to shortest (so all you need to do is sort).
As has been mentioned already, you've specified no information about your scheduling problem, so it is hard to help beyond this (as no universally optimal and efficient scheduler exists).
也许 Stony Brook 算法存储库的作业调度部分可以提供帮助你。
Maybe the Job Scheduling Section of the Stony Brook Algorithm Repository can help you.