摘要
In order to investigate more realistic group scheduling problems with position-dependent effects,the model of general position-dependent group scheduling is proposed,where the actual group setup times and actual processing times are described by general functions of the normal group setup time and position in the sequence.These general functions are not assumed to have specific function structures,and are not restricted to be monotone.By mathematical analysis and proof,each considered problem is decomposed into a group scheduling process and a job scheduling process,and each scheduling process is transferred into the classic assignment problem or the classic single-machine sequence problem,and then the computational complexity to solve the considered problem is analyzed.Analysis results show that,even with general position-dependent job processing times,both the single machine makespan minimization group scheduling problems and the parallel-machine total load minimization group scheduling problems remain polynomially solvable.
为了研究更具实际意义的带有位置依赖影响的分组调度决策问题,建立了一般性位置依赖的分组调度模型.在模型中,分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式,且没有要求限制其函数单调性.通过数理逻辑分析和证明,把所研究的问题模型分解为组调度过程和工件调度过程,并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题,进而分析问题求解的计算复杂度.研究表明,即使在一般性位置依赖的模型假设下,单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的.
基金
The National Natural Science Foundation of China (No.71171046)
the Scientific Research Innovation Project for College Graduates in Jiangsu Province(No.CXLX_0162)
