摘要
本文研究加工时间可控并随开工时间简单线性增长的单机最大完工时间排序问题.该问题将加工时间可控排序和加工时间恶化排序两类研究连接到一起.通过比较技术证明了该问题存在满足以下性质的最优解:每个工件的加工时间或者完全压缩,或者完全不压缩;加工时间完全压缩的工件的顺序由一个工件参数和控制变量的函数的递增序给出,完全不压缩的工件在完全压缩的工件之后以任意序加工.通过将问题等价转换为0-1非线性整数规划问题,给出了单机排序问题的贪婪算法.
This paper considers a single machine makespan scheduling problem with con- trollable and simple linear increasing processing times. This problem connects the two streams of literature on machine scheduling, scheduling with controllable processing times and scheduling with deteriorating processing times. By comparison technique, we prove that for this problem there exists an optimal solution such that the processing time of each job is either fully reduced or not reduced at all, and the optimal sequence is such that the fully controlled jobs are processed in the increasing order of a function value of the parame- ters and control decision of each job, and the uncontrolled jobs are processed in arbitrarily sequence after the fully controlled jobs. By formulating this scheduling problem as a 0-1 nonlinear programming problem, we give a greedy algorithm.
出处
《应用数学学报》
CSCD
北大核心
2012年第4期617-625,共9页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金(61173061
79870091)
湖北文理学院规划(2009YA010)资助项目
关键词
单机最大完工时间排序
可控加工时间
恶化加工时间
0-1非线性整数规划
贪婪算法
single machine makespan scheduling
controllable processing times
deteriorating processing times
0-1 non-linear programming
greedy algorithm
