带有工件实际加工时间上界的调度问题研究  

Scheduling with Actual Job-Processing-Time Upper Bound

作　　者：虞先玉[1] 游运[1] 温荣生[1] 

机构地区：[1]东华理工大学理学院,江西南昌330000

出　　处：《东华理工大学学报（自然科学版）》2012年第4期443-448,共6页Journal of East China University of Technology(Natural Science)

基　　金：江苏省普通高校研究生科研创新计划项目(CXLX_0162)

摘　　要：为了研究更具实际意义位置依赖的单机调度和平行机调度决策问题,建立了带有上界限制的一般性位置依赖工件加工时间模型。在模型中,工件实际加工时间表示为初始加工时间和调度位置的一般函数。此类函数没有特殊函数形式和函数单调性的限制,且其函数值不能超过给定上界。对于单机调度问题和平行机调度问题,研究目标函数分别为最小化总完工时刻和最小化机器总负荷。通过分析证明和把所研究的问题模型转化为经典任务分派问题,进而分析得到求解各个问题的计算复杂度。研究表明,在带有上界限制的一般性位置依赖的工件加工时间模型假设下,所研究调度问题都是多项式时间可解的。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.

关 键 词：调度 位置依赖 上界约束 总完工时刻 总负荷 

分 类 号：F406.2[经济管理—产业经济] TP301[自动化与计算机技术—计算机系统结构]