摘要
主要研究带准备时间的两台同类机已知工件最大加工时间的半在线排序问题,目标函数极小化最大机器完工时间和极小化最大工件完工时间.对此问题给出了竞争比为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
出处
《浙江大学学报（理学版）》
CAS
CSCD
北大核心
2008年第4期395-399,共5页
Journal of Zhejiang University（Science Edition）
关键词
排序
同类机
半在线算法
机器准备时间
竞争比
scheduling problem
uniform machines
semi on-line algorithm
set-up time
competitive ratio
