带截止日期的单机调度
Single machine scheduling with deadlines
我正在寻找解决作业排列的好算法，这样如果作业按该顺序处理，那么每个作业都会在截止日期前完成。
设置 {j1,j2, ... , jn} 个 n 个作业，并给出每个作业的处理时间 t 和截止日期 d。你能推荐任何可能的算法吗？
您的情况下的最佳调度算法是最早截止日期优先 (Wiki)。因此，您按截止日期对工作进行排序，并从最早到最远的开始。事实证明，如果存在不违反最后期限的可行时间表，EDF 会找到它。
如果您的作业具有优先级（权重），则会遵循类似的算法。请参阅最大利润计划 (MPS)。
这里是 MPS 的实现：MPS C++ Code.
我正在寻找解决作业排列的好算法，这样如果作业按该顺序处理，那么每个作业都会在截止日期前完成。
设置 {j1,j2, ... , jn} 个 n 个作业，并给出每个作业的处理时间 t 和截止日期 d。你能推荐任何可能的算法吗？
您的情况下的最佳调度算法是最早截止日期优先 (Wiki)。因此，您按截止日期对工作进行排序，并从最早到最远的开始。事实证明，如果存在不违反最后期限的可行时间表，EDF 会找到它。
如果您的作业具有优先级（权重），则会遵循类似的算法。请参阅最大利润计划 (MPS)。
这里是 MPS 的实现：MPS C++ Code.