Algorithms for semi on-line multiprocessor scheduling problems |
| |
Authors: | He Yong Yang Qi-fan Tan Zhi-yi Yao En-yu |
| |
Institution: | (1) Department of Mathematics, Zhejiang University, 310027 Hangzhou, China;(2) Department of System Science & Engeering, Zhejiang University, 310027 Hangzhou, China |
| |
Abstract: | 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.
Project supported by the National Natural Science Foundation of China (Nos. 19701028 and 19971078) and National 973 Research
Project of China. |
| |
Keywords: | analysis of algorithm on-line scheduling worst-case ratio |
本文献已被 万方数据 SpringerLink 等数据库收录! |
|