Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Minimizing Total Weighted Completion Time on Two Dedicated Processors with Preemptive Multiprocessor Tasks

SpeakerCeyda Oguz

Co-authorXiangtong Qi

We consider scheduling preemptive multiprocessor tasks on two dedicated processors to minimize total weighted completion time. We first show that this problem is NP-hard in the strong sense. We then present properties of the optimal schedule. Based on these properties, we propose a heuristic algorithm and analyze its average performance by a computational experiment. The results suggest that the heuristic algorithm is both efficient and effective with a relative error less than 2%.