带准备时间的两台同类机已知工件总加工时间的半在线排序问题的近似算法  

Algorithms for semi on-line scheduling problems on two uniform machines with set-up time where the total processing time is known in advance

作　　者：华荣伟[1] 洪哲[2] 

机构地区：[1]浙江医学高等专科学校,浙江杭州310053 [2]浙江科技学院,浙江杭州310023

出　　处：《浙江大学学报（理学版）》2008年第4期395-399,共5页Journal of Zhejiang University（Science Edition）

摘　　要：主要研究带准备时间的两台同类机已知工件最大加工时间的半在线排序问题,目标函数极小化最大机器完工时间和极小化最大工件完工时间.对此问题给出了竞争比为2的近似算法,并证明了不存在竞争比小于1+32的近似算法.Semi onvline scheduling problems on two uniform parallel machines with set-up time are considered, where the total processing time is known in advance, to minimize the maximum machine completion time and to minimize the maximum job completion time. Algorithms with competitive ratio of √2 are presented for the considered problems. It is also shown that no algorithm exists that has a competitive ratio smaller than 1＋√3/ 2

关 键 词：排序 同类机 半在线算法 机器准备时间 竞争比 

分 类 号：O223[理学—运筹学与控制论]