文献类型：期刊文章

作　　者：彭南南[1] 张玉忠[1] 柏庆国[1] 王成飞[1]

PENG Nannan;ZHANG Yuzhong;BAI Qingguo;WANG Chengfei(Institute of Operations Research,School of Management,Qufu Normal University,Rizhao 276826,Shandong,China)

机构地区：[1]曲阜师范大学管理学院运筹学研究院,山东日照276826

出　　处：《运筹学学报》

基　　金：国家自然科学基金(Nos.11771251;71771138;71672166;71804089);山东省自然科学基金(No.ZR2017MG009);泰山学者工程专项经费

年　　份：2019

卷　　号：23

期　　号：1

起止页码：111-118

语　　种：中文

收录情况：BDHX、BDHX2017、JST、MR、ZGKJHX、ZMATH、核心刊

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

关 键 词：分批排序  在线算法  同类机 竞争比 一致性

分 类 号：O223]