algorithm - 贪心算法 : highest value first vs earliest deadline first

Question

假设我们有一组 n要执行的作业，每个作业都需要单位时间。在任何时候，我们都只能提供一份工作。职位i , 1<=i<=n当且仅当它不迟于截止日期执行时，我们才能获利。

如果存在至少一个序列允许集合中的每个作业不迟于它们的截止日期执行，我们就可以完成一组可行的作业。 “最早期限优先”是可行的。

表明贪心算法是最优的:在每一步中添加尚未考虑的作业中具有最高利润值的作业，前提是所选择的作业集仍然可行。

必须先做这件事:首先表明总是可以重新安排两个可行序列(一个由贪婪算法计算)，同时安排两个序列共有的每个作业.这个新序列可能包含间隙。

更新

我创建了一个似乎反驳该算法的示例:

假设有 4 个工作:

• 作业 A 的利润为 1，持续时间为 2，截止日期在第 3 天之前；
• 工作 B 的利润为 4，持续时间为 1，截止日期在第 4 天之前；
• 工作 C 的利润为 3，持续时间为 1，截止日期在第 3 天之前；
• 工作 D 的利润为 2，持续时间为 1，截止日期在第 2 天之前。

如果我们先使用利润最高的贪心算法，那么我们只会得到作业B和C。但是，如果我们先执行deadline，那么我们可以得到所有的作业，顺序是CDB

不确定我是否以正确的方式处理这个问题，因为我创建了一个例子来反驳问题想要什么

Answer 1

这个问题看起来像 Job Shop Scheduling，它是 NP 完全的(这意味着没有最优的贪心算法——尽管自 70 年代以来专家们一直在努力寻找一个)。 Here's a video在该用例的更高级形式上，正在使用贪婪算法和局部搜索来解决。

如果我们假设您的用例确实可以放宽到作业车间调度，那么有许多优化算法可以提供帮助，例如元启发式算法(包括本地搜索，例如禁忌搜索和模拟退火)、(M)IP、动态编程、约束编程……有这么多选择的原因是没有一个是完美的。我更喜欢元启发式方法，因为它们在我见过的所有研究挑战中都超过了其他方法。