Rescheduling on identical parallel machines with machine disruptions to minimize total completion time
Rescheduling on identical parallel machines with machine disruptions to minimize total completion time
复制标题
DOI：
10.1016/j.ejor.2016.01.045
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
Yunqiang Yin;T. Cheng;Dujuan Wang
中科院分区：
文献类型：
--
作者：
Yunqiang Yin;T. Cheng;Dujuan Wang
我们考虑一组工作已经被分配到相同的并行机，受到干扰的目标是最小化总完成时间的调度问题。当机器中断发生时，受影响的工作需要重新安排，以便不造成相对于原始时间表的过度时间表中断。如果原计划中的任何作业的完成时间可以被视为相关作业的隐含到期日，则进度中断可以通过最大时间偏差或总虚拟误工来度量。我们专注于调整后的时间表和时间表中断的总完成时间之间的权衡，找到帕累托最优的解决方案。我们表明，这两个变种的问题是NP-硬的强意义上的机器的数量被认为是输入的一部分，和NP-硬的机器的数量是固定的。此外，我们开发了伪多项式时间的解决方案算法的两个变种的问题与固定数量的机器，建立他们是NP-硬在普通意义上。对于变量的时间表中断建模为总的虚拟迟到，我们还表明，机器中断只发生在一台机器上的情况下，承认一个二维的完全多项式时间近似方案。我们进行了广泛的数值研究，以评估所提出的算法的性能。
We consider a scheduling problem where a set of jobs has already been assigned to identical parallel machines that are subject to disruptions with the objective of minimizing the total completion time. When machine disruptions occur, the affected jobs need to be rescheduled with a view to not causing excessive schedule disruption with respect to the original schedule. Schedule disruption is measured by the maximum time deviation or the total virtual tardiness, given that the completion time of any job in the original schedule can be regarded as an implied due date for the job concerned. We focus on the trade-off between the total completion time of the adjusted schedule and schedule disruption by finding the set of Pareto-optimal solutions. We show that both variants of the problem are NP-hard in the strong sense when the number of machines is considered to be part of the input, and NP-hard when the number of machines is fixed. In addition, we develop pseudo-polynomial-time solution algorithms for the two variants of the problem with a fixed number of machines, establishing that they are NP-hard in the ordinary sense. For the variant where schedule disruption is modeled as the total virtual tardiness, we also show that the case where machine disruptions occur only on one of the machines admits a two-dimensional fully polynomial-time approximation scheme. We conduct extensive numerical studies to evaluate the performance of the proposed algorithms.