工件加工时间增加的排序问题(1‖C_(max))  

SCHEDULING TO MINIMIZE MAKESPAN ABOUT INCREASE OF PROCESSING TIMES

作　　者：张峰[1] 

机构地区：[1]上海第二工业大学应用数学系,上海200041

出　　处：《高校应用数学学报（A辑）》2001年第2期228-234,共7页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金! (1 9771 0 57)

摘　　要：讨论了工件加工时间随工件开工时间线性增加的排序问题 ,考虑的目标函数是最大完工时间 .证明了加工时间是简单线性增加情况下最大完工时间问题是多项式时间可解的 .对于加工时间是一般线性增加情况 ,研究了最优排序的性质 。This paper discusses that the job processing time is a linear increasing function of their starttime.First,the makespan problem on the simple linear increasing is studied,and the problem remains polynomial time solvable,then the makespan problem on the general linear increasing is considered.Under two special cases this problem is proved to be polynomial time solvable.

关 键 词：排序 加工时间线性增加 最大完工时间 多项式时间可解 工件 

分 类 号：O223[理学—运筹学与控制论]