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

摘要：

针对研究了两代理情形下的单机排序问题，考虑两类问题：一是在误工工件个数不超过一个给定值的情况下使得总误工最小，另一个是代理 A的工件加工时间和权重满足反一致关系时，在误工工件个数不超过一个给定值的情况下使得总加权完工时间之和最小。对于这两类问题采用动态规划方法分别给出最优性质和相应的拟多项式时间算法。

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

所属期刊栏目：52

分类号：TP29;O223(自动化技术及设备)

资助基金：国家自然科学基金No.61302180，No.11401065；中国博士后基金No.2013M540698，No.2014T70854；重庆市教委自然科学基金No.KJ120624，No.KJ130606；重庆市自然科学基金No.cstc2014jcyjA00003；重庆师范大学重点项目基金No.2011XLZ05。

在线出版日期：2016-08-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：32-36