摘要
讨论工件有不同准备时间,加工允许中断的同速机调度问题,目标函数为最小化时间表长.提出了一个算法,并证明了该算法为最优算法,该算法中工件中断的次数至多为Nn次,计算的复杂度为O(Nnlogn).最后给出一个实例加以说明.
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.
出处
《北京师范大学学报（自然科学版）》
CAS
CSCD
北大核心
2008年第5期465-468,共4页
Journal of Beijing Normal University(Natural Science)
基金
国家"九七三"重大基础研究计划基金(2002CB312200)
国家自然科学基金资助项目(60774049)
关键词
同速机调度
中断
准备时间
时间表长
最优算法
identical machine scheduling
preemption
release times
makespans
optimal algorithm
