摘要
本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.
This paper investigates a semi-online scheduling problem with combination of two types of information on two identical parallel machines with non-simultaneous machine available times. The jobs arrive sorted by non-increasing sizes and the total processing time of all jobs is known in advance, the goal is to minimize the maximum machine completion time. Its lower bound is analyzed and an optimal algorithm with competitive ratio 7/6 is presented.
出处
《运筹学学报》
CSCD
2009年第4期83-89,共7页
Operations Research Transactions
基金
浙江省教育厅资助项目(20070524)
关键词
运筹学
排序
半在线
平行机
竞争比
Operations research, scheduling, semi-online, parallel machine, competitive ratio
