영문내용
(English Abstract) |
In parallel job scheduling, each job can be executed simultaneously on multiple machines at a time. Thus in the input instance, a job requires the number of machines on which it shall be processed. The algorithm should determine not only the execution order of jobs but also the machines on which the jobs are executed.
In this paper, when the jobs have deadlines, the problem is to maximize the total work of jobs which is completed by their deadlines. The problem is known to be strongly NP-hard [5] and we investigate the approximation algorithms for the problem.
We consider a model in which the algorithm can have more machines than the adversary. With this advantage, the problem is how good solution the algorithm can produce against the optimal algorithm. |
