两台同型平行机的复合半在线排序问题  

Semi-online scheduling problem on two identical parallel machines with combined partial information

作　　者：谭金芝[1] 

机构地区：[1]温州大学数学与信息科学学院,浙江温州325035

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

基　　金：浙江省教育厅科研项目(20070524);温州大学校级资助项目(2005L001)

摘　　要：研究了两台同型平行机的一个复合半在线排序问题.即对已知工件加工时间递减和实例最优值,目标为极大化机器最早完工时间的复合半在线排序模型,分析了它的下界,并给出了竞争比为9/8的最优算法.A semi-online scheduling problem on two identical parallel machines with combination of two types of information is considered. The iobs arrive sorted by non-increasing sizes and the optimal objective function value is known in advance. The goal is to maximize the minimum machine completion time. Its lower bound is analyzed and an optimal algorithm with competitive ratio 9/8 is presented.

关 键 词：半在线排序 近似算法 竞争比 

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