摘要
本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.
This paper considers a parallel machine total weighted completion time scheduling problem with controllable and simple linear increasing processing times.We prove that for this NP-hard problem,there exists an optimal solution such that the processing time of each job is either fully reduced or not reduced at all,and for every machine,the optimal job sequence is defined by the increasing order of a certain function of the parameters and control decision of each job.By formulating the problem as a 0-1 nonlinear programming problem,we give a greedy algorithm for the scheduling problem.
出处
《应用数学学报》
CSCD
北大核心
2010年第4期741-749,共9页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金(70771078
70471034
A0324666)
襄樊学院规划(2009YA010)资助项目
关键词
平行机排序
可控的加工时间
恶化的加工时间
0-1非线性整数规划
贪婪算法
parallel machine scheduling
controllable processing time
deteriorating processing time
0-1 non-linear programming
greedy algorithm
