scheduling - 具有作业执行时间、截止日期和处罚的作业排序

Question

如果作业错过截止日期，则有 N 个作业具有执行时间、截止日期和处罚。每项工作的执行时间、截止日期和罚款可能会有所不同。当时只能完成一项工作。所有的工作都必须完成。任务是对惩罚最小的工作（计划）进行排序。

您对算法有任何想法，甚至可以分享一些代码示例吗？我真的被这个任务困住了。

Answer 1

问题的名称是“作业排序问题”，虽然我没有自己的示例可以分享，但您可以查看此https://www.geeksforgeeks.org/job-sequencing-problem-set- 1-贪心算法/

Answer 2

我想当一个工作错过它的最后期限时的惩罚是一个常数 w_j，它取决于工作 j 而不是它的迟到值。在一般情况下，问题是 NP Hard（它是1||sum_j w_j U_j经典alpha|beta|gamma表示法）。在特殊情况下它是多项式的，所有权重 w_j 都相等（最小化延迟作业的数量）。

您可能会找到许多非常有效的针对特定问题的算法来解决这个特定问题。如果您对解决此问题的通用公式感兴趣，您可以尝试 CP Optimizer [1]，在 OPL 中，解决该问题的公式如下所示：

int n = ...;
int  dd[j in 1..n] = ...; // Deadline for job j
int  pt[j in 1..n] = ...; // Processing time for job j
float w[j in 1..n] = ...; // Penalty for late job j

dvar interval job[j in 1..n] size pt[j]; // Decision variables

minimize sum(j in 1..n) ( w[j]*(endOf(job[j])>=dd[j]) );
subject to {
  noOverlap(all(j in 1..n) job[j]);
}

这是 CP Optimizer 中利用可选间隔变量的概念的一个更好的公式：您最大化被限制在截止日期之前结束的已执行间隔/活动的等待总和：

int n = ...;
int  dd[j in 1..n] = ...; // Deadline for job j
int  pt[j in 1..n] = ...; // Processing time for job j
float w[j in 1..n] = ...; // Penalty for late job j

dvar interval job[j in 1..n] optional in 0..dd[j] size pt[j]; // Decision variables

minimize n - sum(j in 1..n) ( w[j]*presenceOf(job[j]) );
subject to {
 noOverlap(all(j in 1..n) job[j]);
}

[1] P. Laborie、J. Rogerie、P. Shaw、P. Vilím。用于调度的 IBM ILOG CP 优化器。约束日志。2018 年 4 月，第 23 卷，第 2 期，第 210-250 页。http://ibm.biz/Constraints2018。