原始工件的完工时间限制下的最小化最大延误时间的重新排序  

Rescheduling to Minimize Maximum Lateness Under a Limit on the Makespan of the Original Jobs

作　　者：慕运动[1] 谷存昌[1] 

机构地区：[1]河南工业大学理学院,河南郑州450001

出　　处：《数学的实践与认识》2012年第18期110-116,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金NSFC(10671183);河南自然科学基金NSFHN(112300410078);河南教育厅自然科学基金(2011B110008);河南工业大学博士科研基金

摘　　要：考虑由两个代理引起的重新排序问题,其中每个代理都在公共的加工资源下完成各自的不可中断加工的工件.每个代理要求在仅依赖工件的完工时间时最小化某一个特定的目标函数.考虑在原始工件的完工时间限制下的两个代理的单机最小化最大延误时间的重新排序问题.证明了该问题能在多项式时间或者拟多项式时间内解决.We consider the rescheduling problems arising when two agents, each with a set of nonpreemptive jobs, compete to perform their respective jobs on a common processing function. Each agent wants minimize a certain objective function, which depends on the completion time of its jobs only. In this paper, we consider the two agents rescheduling problem for jobs on a single machine to minimize maximum lateness under a limit on the makespan of the original jobs. We show that the considered problems can be solved in polynomial time or pseudopolynomial time.

关 键 词：重新排序 多代理 目标函数 延误时间 完工时间 错位 

分 类 号：O223[理学—运筹学与控制论]