摘要
研究了两台同型平行机的一个复合半在线排序问题.即对已知工件加工时间递减和实例最优值,目标为极大化机器最早完工时间的复合半在线排序模型,分析了它的下界,并给出了竞争比为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.
出处
《浙江大学学报（理学版）》
CAS
CSCD
北大核心
2008年第5期507-510,516,共5页
Journal of Zhejiang University（Science Edition）
基金
浙江省教育厅科研项目(20070524)
温州大学校级资助项目(2005L001)
关键词
半在线排序
近似算法
竞争比
semi-online scheduling
approximation algorithm
competitive ratio
