复合两信息的同类机半在线排序问题  

A Semi-online Scheduling Problem with Combination of Double Information on Two Uniform Machines

作　　者：谭金芝[1] 

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

出　　处：《温州师范学院学报》2005年第5期6-10,共5页Journal of Wenzhou Teachers College(Philosophy and Social Science Edition)

摘　　要：研究了两台同类机的一个半在线排序问题,当预先知道所有工件的加工时间总和(sum)与最大工件的加工时间(max)及目标为极大化最小机器完工时间的情形时,证明了此问题的竞争比为(3s+2)/(2s+2)的半在线算法.This paper investigates a semi-online scheduling problem with combination of double information on two uniform machines. We assume that the total processing time and the largest processing time are known in advance, and the goal is to maximize the minimum machine completion time. We present an approximate algorithm SM while prove its competitive ratio of （3s＋2）/（2s＋2） .

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

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