Rescheduling for Multiple New Orders
Rescheduling for Multiple New Orders
复制标题
DOI：
10.1287/ijoc.1060.0209
复制
发表时间：
2007-10
期刊：
影响因子：
--
通讯作者：
Nicholas G. Hall;Zhixin Liu;C. Potts
中科院分区：
文献类型：
--
作者：
Nicholas G. Hall;Zhixin Liu;C. Potts
当一组新作业到达时，已在一台计算机上调度了一组原始作业，但未进行处理。决策者需要在不过度更改的情况下将新工作添加到现有计划中。目标是最小化作业的最大延迟，满足由原始作业的最大时间变化限制来建模的客户服务需求。由于原始作业的调度可能是任意的，因此该问题模拟了重复到达新作业的多个中断。我们证明了即使没有新的作业到达，这个调度问题也是棘手的。我们描述了几种近似算法，并分析了它们在最坏情况下的性能。接下来，我们开发了一种分支定界算法，它使用可变邻域下降算法来获得初始上界、我们建立的几个优势性质以及基于问题的抢占松弛的下界方案。分支定界算法在60 CPU秒内解决99.9%的随机生成实例，最多可处理1000个作业。我们的工作首次证明了对大规模、棘手的重新调度问题进行优化是可能的。更广泛地说，它将文献的重点重新放在调度问题上，而不是重新调度问题。
Aset of original jobs has been scheduled on a single machine, but not processed, when a set of new jobs arrives. The decision maker needs to insert the new jobs into the existing schedule without excessively changing it. The objective is minimization of the maximum lateness of the jobs, subject to a customer service requirement modeled by a limit on the maximum time change of the original jobs. Because the schedule of the original jobs can be arbitrary, this problem models multiple disruptions from repeated new job arrivals. We show that this scheduling problem is intractable, even if no new jobs arrive. We describe several approximation algorithms and analyze their worst-case performance. Next, we develop a branch and bound algorithm that uses a variable neighborhood descent algorithm to obtain an initial upper bound, several dominance properties that we establish, and a lower bounding scheme based on a preemptive relaxation of the problem. The branch and bound algorithm solves 99.9% of randomly generated instances with up to 1,000 jobs within 60 CPU seconds. Our work demonstrates for the first time that optimization of large scale, intractable rescheduling problems is possible. More generally, it refocuses the literature on scheduling problems towards rescheduling issues.