三台平行同型机的一个半在线排序算法  

Semi Online Scheduling on Three Identical Machines

作　　者：蔡圣义[1] 

机构地区：[1]温州师范学院数学系,浙江温州325003

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

摘　　要：本文研究三台平行同型机的一个半在线排序算法,我们假设工件的最大加工时间预先知道,我们将给出一个竞争比为（1+(?)73）/6≈1.5907的半在线算法,同时证明对该问题的这一半在线情形,任意半在线算法的竞争比至少是(?)2.This paper investigates a semi-online scheduling on three identical machines. We assume that the largest processing time of all jobs is known in advance. We present an algorithm with competitive ratio (1 +(?)73)/6≈1. 5907 while the lower bound is (?)2.

关 键 词：平行同型机 半在线排序算法 竞争比 最大加工时间 Ls算法 工件长复 

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