论文部分内容阅读
为了研究更具实际意义的带有位置依赖影响的分组调度决策问题,建立了一般性位置依赖的分组调度模型.在模型中,分组实际发动时间和工件的实际加工时间被表示成初始时间和调度位置的一般函数.此类函数没有被假设为特殊函数形式,且没有要求限制其函数单调性.通过数理逻辑分析和证明,把所研究的问题模型分解为组调度过程和工件调度过程,并把每个调度过程分别转化为经典任务分派问题和单机排序调度问题,进而分析问题求解的计算复杂度.研究表明,即使在一般性位置依赖的模型假设下,单机最小化时间表长的分组调度问题和平行机最小化总负荷的分组调度问题仍然是多项式可解的.
In order to study more practical problem of group scheduling decision with location-dependent influence, a general location-dependent packet scheduling model is established, in which the actual time of grouping and the actual processing time of the workpiece are expressed as initial time and schedule Which is not assumed to be a special function form and does not require the monotonicity of the function to be restricted.According to the mathematical logic analysis and the proof, the model of the problem under study is decomposed into the group scheduling process and the workpiece scheduling process, and the Each scheduling process is transformed into classical task assignment problem and stand-alone scheduling problem respectively, and then the computational complexity of problem solving is analyzed.The results show that even under the general location-dependent model assumption, And parallel machine to minimize the total load of the packet scheduling problem is still polynomial solvable.