排序问题P_2|prmp|C_(max)在中断—重复模型下的调度

An Algorithm for P_2｜prmp｜C_(max) to the Preempt-repeat Model

对于传统的中断—恢复模型下的P2|prmp|Cmax问题,已有最优调度规则。但中断—恢复模型并不是一般意义下的中断模型。在某些情况下,被中断的任务不能被简单的恢复加工,而是在该任务被重新加工之前必须有一定的延迟时间。延迟可能是该项任务的一部分(或者是全部)需要返工的时间。本文在研究了排序问题P2|prmp|Cmax在中断—重复模型下的调度,指出对于选择哪一个任务被中断的问题是NP-hard的;而对于如何处理被中断的任务的问题,指出当被中断任务的最初被加工时间由Xj增加为Xj+ΔXj=Xj1-12jαn时,可使得两台处理机的时间表长相等,从而达到最优。最优时间表长为:Cm*ax=12∑j=1pj+jαXj2-jα。最后给出了在中断-重复模型下的调度规则。

There has been the optional algorithm for the problem P2｜prmp｜Cmax. But the traditional preemptresume model is not the usual delay condition. Sometimes, the preemption can not be simply resumed, instead there must be some delay before the work is reprolessed. The delay may be the time for reprocess that the pait of the work （or whole） needs. In this thesis, we study the problem P2｜prmp｜Cmaxto the preempt-repeat model. We point out that the problem which job should be selected to preempt is NP-hard. And for the problem of how to deal with the selected job, we point out that when the original work time of the preempted job is changed from Xj to Xj ＋ △xj=Xj/（1-1/2aj） , the process-time of the two machines will be equal, and the optimal time length Cmax^＊=1/2n∑j=1pj＋ajxj/（2-aj） At last, an algorithm for P2｜prmp｜Cmax is given.