带机器准备时间的m台平行机在线和半在线排序  

On-line and Semi-online Scheduling Problems on m Parallel Machines with Non-simultaneous Machine Available Times

作　　者：谭金芝[1] 

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

出　　处：《应用数学》2008年第3期518-523,共6页Mathematica Applicata

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

摘　　要：本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.This paper investigates online and semi-online scheduling problems on m identical parallel machines with non-simultaneous machine available times. The objective function is to maximize the minimum machine completion time. In the online version we prove that the competitive ratio of algorithm LS is m. In the semi-online version,two problems are studied, where the total processing time of all jobs and the largest processing time of all jobs being known in advance. For each problem,we analyze its lower bound and give optimal algorithm with the competitive ratio m -1 .

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

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