摘要
为了研究更具实际意义位置依赖的单机调度和平行机调度决策问题,建立了带有上界限制的一般性位置依赖工件加工时间模型。在模型中,工件实际加工时间表示为初始加工时间和调度位置的一般函数。此类函数没有特殊函数形式和函数单调性的限制,且其函数值不能超过给定上界。对于单机调度问题和平行机调度问题,研究目标函数分别为最小化总完工时刻和最小化机器总负荷。通过分析证明和把所研究的问题模型转化为经典任务分派问题,进而分析得到求解各个问题的计算复杂度。研究表明,在带有上界限制的一般性位置依赖的工件加工时间模型假设下,所研究调度问题都是多项式时间可解的。
In order to investigate more realistic single-machine and parallel-machine scheduling problems with po- sition-dependent effect, the model of general position-dependent group scheduling is proposed, where the actual job processing times are described by general functions of the normal group setup time and position in the se- quence; these general functions are not assumed to have specific function structure, and are assumed to have up- per bound. By mathematical analysis and transferring the considered problems into the classic assignment prob- lems, the computational-complexity results of solving the considered problems are analyzed. Analysis results show that, even with upper bounded position-dependent job processing times, all the considered problems are still poly- nomially solvable.
出处
《东华理工大学学报（自然科学版）》
CAS
2012年第4期443-448,共6页
Journal of East China University of Technology(Natural Science)
基金
江苏省普通高校研究生科研创新计划项目(CXLX_0162)
