最小化误工工件个数的两代理单机排序问题  

Two-agent scheduling on single machine to minimize number of tardy jobs

作　　者：张新功[1] 王慧[1] 柏世坤 

机构地区：[1]重庆师范大学数学学院,重庆401331

出　　处：《计算机工程与应用》2016年第14期32-36,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61302180;No.11401065);中国博士后基金(No.2013M540698;No.2014T70854);重庆市教委自然科学基金(No.KJ120624;No.KJ130606);重庆市自然科学基金(No.cstc2014jcyj A00003);重庆师范大学重点项目基金(No.2011XLZ05)

摘　　要：针对研究了两代理情形下的单机排序问题,考虑两类问题:一是在误工工件个数不超过一个给定值的情况下使得总误工最小,另一个是代理A的工件加工时间和权重满足反一致关系时,在误工工件个数不超过一个给定值的情况下使得总加权完工时间之和最小。对于这两类问题采用动态规划方法分别给出最优性质和相应的拟多项式时间算法。In this paper, two scheduling problems for two-agent scheduling are considered. One is to minimize total tardiness of agent A , while the number of late jobs must be kept less than or equal to a fixed value. Another is to minimize total weighted completion times of agent A , while the number of late jobs must be kept less than or equal to a fixed value, where the jobs of agent A satisfy the anti-agreeable relation. Some properties of the optimal schedule are provided for the two problems, and it presents pseudo-polynomial time algorithms of the proposed problem, respectively.

关 键 词：排序 两个代理 拟多项式时间算法 动态规划 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置] O223[自动化与计算机技术—控制科学与工程]