Minimizing Total Weighted Completion Time on Two Dedicated Processors with Preemptive Multiprocessor Tasks
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%.