技术进展国际期刊
开放获取

抽象的

最小化单台机器的完工时间和发布日期

EO 奥耶通吉、AE 奥卢莱耶

本文考虑了在具有发布日期的单台机器上最小化完工时间的单标准调度问题。该问题本质上是 NP-Hard，因此需要近似算法来解决该问题。针对该问题提出了一种算法（称为 NAL）。将NAL算法与分支定界（BB）方法以及从文献中选择的测试算法（AEO）进行比较。这三种解决方法在一组随机生成的问题（范围从 10 到 500 个作业）上进行了测试。实验结果表明，该算法与 BB 方法具有竞争性，并且优于 AEO 算法。