论文部分内容阅读
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.
In the classical multiprocessor scheduling problems, it is assumes that the problems were considered in off | line or on | line environment. But in practice, problems are often not really off | line or on | line but some means 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.