arXiv:2205.07537v4 宣布类型: 替换 摘要: 工厂调度问题是组合优化领域一个广为人知且具有挑战性的问题，其中共享同一台机器的任务需要按照顺序排列，以便可以尽可能早地完成包含的任务。在本文中，我们研究了将问题分解成时间窗口的方法，通过多轮Answer Set Programming(ASP)求解来依次调度和优化这些操作。从计算角度来看，分解的目标是将高度复杂的调度任务分割成更容易管理的子问题，这些子问题具有均衡的操作数量，以便在运行时间内找到高质量甚至是优化的局部解。我们设计并研究了各种分解策略，涉及到时间窗口的数量和大小以及选择操作的方法。此外，我们还将时间窗口的重叠和压缩技术纳入迭代调度过程中，以克服仅在窗口范围内进行部分调度而导致的优化限制。在不同JSP基准数据集上的实验表明，通过多轮ASP求解进行依次优化在严格的时间限制内能产生明显更好的调度结果。特别是，我们将初始解分解成时间窗口后发现，可以提高解的质量。