University of Hong Kong
In this paper, the authors consider a benefit model for on-line preemptive multiprocessor scheduling. In this model, each job arrives with its own benefit function and execution time. The flow time of a job is the time between its arrival and its completion. The benefit function determines the benefit gained for any given flow time. The goal is to maximize the total benefit gained only by the jobs that meet their deadlines. In order to achieve this goal, a variety of approximation algorithms and their applications in multiprocessor scheduling were studied.