无界平行分批机器上的在线时间调度：最小化最大完成时间

"Online over time scheduling on unbounded p-batch machines to minimize the makespan: A survey" 这篇论文的标题是“在线依时间调度无界平行分批机器以最小化时间表长：一项综述”，它主要关注的是在排序理论中的一个活跃研究领域——在线排序。在这一领域中，特别是在无界平行分批机器上最小化时间表长（也称为最大完工时间或 Makespan）的模型具有重要意义。无界平行分批机器指的是可以无限次地接受新批次工作的多台机器，每个批次中的工作可以在任意一台机器上同时进行。 论文的作者对这一领域的研究进行了详尽的回顾，分析了关于在线依时间调度无界平行分批机器以优化 Makespan 的现有研究成果。在线调度问题的特点是决策必须在接收到任务信息的那一刻做出，而不是在事先知道所有任务的情况下规划。这种实时性增加了问题的复杂性和挑战性。 文章摘要中提到了几个关键点，包括： 1. **在线排序**：这是调度理论的一个分支，其中任务的到达时间和需求是在运行时确定的，要求算法能即时做出决策。 2. **无界平行分批机器**：这种模型允许无限数量的工作批次被分配到多台机器上，每批可以并行处理，但每个批次的作业数量可能是变化的。 3. **最小化时间表长**：目标是尽可能减少所有任务完成所需的最大时间，也就是 Makespan，这对于优化生产效率和减少等待时间至关重要。 4. **竞争比**：这是一个衡量在线算法性能的指标，指的是最优离线解决方案与在线算法解决方案的 Makespan 比值的最坏情况。 论文还提出了未来研究的一些开放性问题，可能包括如何设计更有效的算法来降低 Makespan，或者探索新的性能度量以更好地理解这些在线调度策略的局限性和潜在改进空间。 在更深入的研究中，作者可能会探讨不同类型的释放日期和处理时间分布如何影响调度策略，以及如何通过预处理或调整任务属性来优化调度。此外，可能还会涉及随机性和不确定性因素，例如任务到达的随机性、机器故障或性能波动等，这些都是实际生产环境中常见的挑战。 这篇综述论文对于了解无界平行分批机器上的在线调度问题及其最新进展具有重要价值，同时也为该领域的未来研究指明了方向。