Algorithms for multiprocessor scheduling with machine release times
作者:
HANS KELLERER,
期刊:
IIE Transactions
(Taylor Available online 1998)
卷期:
Volume 30,
issue 11
页码: 991-999
ISSN:0740-817X
年代: 1998
DOI:10.1080/07408179808966555
出版商: Taylor & Francis Group
数据来源: Taylor
摘要:
In this paper we present algorithms for the problem of scheduling n independent jobs on m identical machines. As a generalization of the classical multiprocessor scheduling problem each machine is available only at a machine dependent release time. Two objective functions are considered. To minimize the makespan, we develop a dual approximation algorithm with a worst case bound of 5/4. For the problem of maximizing the minimum completion time, we develop an algorithm, such that the minimum completion time in the schedule produced by this algorithm is at least 2/3 times the minimum completion time in the optimum schedule. The paper closes with some numerical results.
点击下载:
PDF (1077KB)
返 回