| 关于单机两个客户竞争排序问题1||∑wAjcAj:fBmax≤Q的一个注记 |
| |
| 引用本文： | 罗文昌,李剑秋.关于单机两个客户竞争排序问题1||∑wAjcAj:fBmax≤Q的一个注记[J].应用数学学报,2011,34(1). |
| |
| 作者姓名： | 罗文昌 李剑秋 |
| |
| 作者单位： | 1. 宁波大学理学院,宁波,315211;浙江大学数学系,杭州,310027
2. 浙江工商大学杭州商学院,杭州,310018 |
| |
| 基金项目： | 国家自然科学基金，宁波大学学科科研基金 |
| |
| 摘 要： | 研究了单机两个客户竞争排序问题1||∑wAjcAj:fBmax≤Q,证明了该问题与问题1|MAi|∑wjcj及问题1|hi,pmtn|∑wjcj之间是相互等价的.对wj=pj时的特殊情形,指出了问题1||∑wAjcAj:fBmax≤Q存在近似比为2的最长处理时间优先算法(LPT)且该界是紧的,对wj任意的一般情形,指出了问题1||∑wAjcAj:fBmax≤Q存在近似比为4+ε的近似算法.当客户B的工件数是常数时,对问题1||∑wAjcAj:fBmax≤Q则给出了伪多项式时间的动态规划算法.此外,指出了问题1||∑wAjcAj:∑wBjcBj ≤ Q具有多项式时间近似方案(PTAS).
|
| 关 键 词： | 两个客户 竞争排序 多个维护 近似算法 |
| 本文献已被 万方数据 等数据库收录！ |
|
