讨论工件有不同准备时间,加工允许中断的同速机调度问题,目标函数为最小化时间表长.提出了一个算法,并证明了该算法为最优算法,该算法中工件中断的次数至多为Nn次,计算的复杂度为O(Nn logn).最后给出一个实例加以说明.
The Identical machine scheduling problem with preemption and release times is considered. The objective is to minimize makespan. An optimal algorithm is proposed to solved this problem. In this algorithm, preemption time is at most Nn, the problem can be solved in O(Nn logn). An example is given to illustrate the algorithmz.