文献类型：期刊文章

作　　者：丁际环[1] 曲桂东[2] 张伟[3] 岳丽[1] 张玉忠[1]

机构地区：[1]曲阜师范大学运筹与管理学院,山东省日照市276800 [2]威海职业学院信息工程系,山东省威海市264200 [3]青岛师范学院数学系,山东省青岛市266071

出　　处：《曲阜师范大学学报（自然科学版）》

基　　金：国家自然科学基金;教育部高校骨干教师项目;山东省中青年学术骨干项目

年　　份：2003

卷　　号：29

期　　号：3

起止页码：1-5

语　　种：中文

收录情况：AJ、CAS、MR、WOS、ZMATH、普通刊

摘　　要：研究带机器准备时间的m台同类机 (uniformmachines)在线和半在线排序问题 ,目标函数为极小化最大机器 (工件 )完工时间 .对于在线情形 ,证明了LS算法的最坏情况为 ρ =( 1+ 5 ) 2 ,m =2 ,1+ 2m - 2 2 ,m≥ 3 ,并且当m =2时 ,LS算法是最好的近似算法 ;当m =2 ,3 ,… ,6时界是紧的 ,特别地 ,当s1 =s2 =… =sm - 1 ,sm ≥ 1时 ,证明了LS算法的最坏情况界为 ρ =( 1+ 5 ) 2 ,m =2 ,3 - 4 (m + 1) ,m≥ 3 ,而且界是紧的 ;对于已知加工时间递减的半在线排序问题 ,证明了LS算法的最坏情况界为 2 - 2 (m + 1) .

关 键 词：在线排序  半在线排序 机器准备时间 同类机 近似算法  最坏情况  LS算法  

分 类 号：O223]