关于单机两个客户竞争排序问题1||∑wAjcAj:fBmax≤Q的一个注记 |
| |
作者姓名: | 罗文昌 李剑秋 |
| |
作者单位: | 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).
|
关 键 词: | 两个客户 竞争排序 多个维护 近似算法 |
本文献已被 万方数据 等数据库收录! |
|