University of Houston

This project considers a benefit model for on-line preemptive multiprocessor scheduling. The goal is to maximize the total benefit. Only the jobs that meet their deadlines can gain benefit. A greedy algorithm with 2-approximation ratio plus a load balancing technique are proposed to be added to an existing benefit-based scheduling algorithm, in order to decrease the idle time for processors by assigning jobs to the processor with least utilization so far. This method will decrease the flow time of some of the jobs, resulting in higher benefits gained by them. Also, performance evaluations of this approach and another benefit-based scheduling algorithm, proposed by other researchers, shows that our solution uses the CPU cycles more efficiently by providing more balanced distribution of the jobs between the processors. Therefore, more jobs can meet their deadlines and add their gained benefits to the total benefit. In addition, the proposed method is computationally less expensive than the other benefit-based method. The proposed method is shown to be more suitable for soft real-time applications with high utilization. Our first paper including the basic idea of this solution has been accepted in the 14th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS ‘08), and selected as one of 4 best papers in the WIP section. The improved version of this method along with simulation-based experimental results is provided in the second paper submitted to the IEEE Real-Time Systems Symposium (RTSS ‘09). We are planning to extend our research by working on some I/O and memory issues of the simulation as well as studying/experimenting more real world applications. Also, we are going to work on the solution from other aspects such as cost effectiveness and obtaining minimum makespan on unrelated machines while maximizing benefit.