Algorithms for semi on-line multiprocessor scheduling problems

作     者：杨启帆 谈之奕 姚恩瑜 何勇 

作者机构：DepartmentofMathematicsZhejiangUniversityHangzhou310027China DepartmentofSystemScience&EngeeringZhejiangUniversityHangzhou310027China 

基　　金：National 973 Researvh Project of China National Natural Science Foundation of China, NSFC, (19701028, 19971078) 

出 版 物：《Journal of Zhejiang University Science》 (浙江大学学报（自然科学英文版）)

年 卷 期：2002年第3卷第1期

页      码：60-64页

摘      要：In the classical multiprocessor scheduling problems, it is assumed that the problems are considered in off\|line or on\|line environment. But in practice, problems are often not really off\|line or on\|line but somehow in between. This means that, with respect to the on\|line problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi on\|line ones. The authors studied two semi on\|line multiprocessor scheduling problems, in which, the total processing time of all tasks is known in advance, or all processing times lie in a given interval. They proposed approximation algorithms for minimizing the makespan and analyzed their performance guarantee. The algorithms improve the known results for 3 or more processor cases in the literature.

主 题 词：analysis of algorithm on\|line scheduling worst\|case ratio 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.1007/BF02881844

馆 藏 号：203598255...