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

作     者：虞先玉 游运 温荣生 YU Xian-yu;YOU Yun;WEN Rong-sheng

作者机构：东华理工大学理学院江西南昌330000 

出 版 物：《东华理工大学学报（自然科学版）》 (Journal of East China University of Technology(Natural Science))

年 卷 期：2012年第35卷第4期

页      面：443-448页

学科分类：120202[管理学-企业管理（含：财务管理、市场营销、人力资源管理）] 12[管理学] 1202[管理学-工商管理] 08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

主　　题：调度 位置依赖 上界约束 总完工时刻 总负荷 

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