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

SCHEDULING TO MINIMIZE MAKESPAN ABOUT INCREASE OF PROCESSING TIMES

讨论了工件加工时间随工件开工时间线性增加的排序问题 ,考虑的目标函数是最大完工时间 .证明了加工时间是简单线性增加情况下最大完工时间问题是多项式时间可解的 .对于加工时间是一般线性增加情况 ,研究了最优排序的性质 。

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.