工件满足一致性的同类机在线分批排序问题

作者：彭南南^*; 张玉忠; 柏庆国; 王成飞

来源：运筹学学报, 2019, 23(01): 111-118.

DOI：10.15960/j.cnki.issn.1007-6093.2019.01.013

• 分批排序
• 在线算法
• 同类机
• 竞争比
• 一致性

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q2|ri<rj?pi≤pj,B=∞, on-line|Cmax,Q2|ri<rj?pi≥pj,B=∞, on-line|Fmax.不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.

• 单位
  曲阜师范大学