Minimizing total completion time in two-processor task systems with prespecified processor allocations

✍ Scribed by Xiaoqiang Cai; Chung-Yee Lee; Chung-Lun Li

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 127 KB
• Volume: 45
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/(sici)1520-6750(199803)45:2<231::aid-nav7>3.0.co;2-9

✦ Synopsis

We consider the problem of scheduling multiprocessor tasks with prespecified processor allocations to minimize the total completion time. The complexity of both preemptive and nonpreemptive cases of the two-processor problem are studied. We show that the preemptive case is solvable in O(n log n) time. In the nonpreemptive case, we prove that the problem is NP-hard in the strong sense, which answers an open question mentioned in Hoogeveen, van . An efficient heuristic is also developed for this case. The relative error of this heuristic is at most 100%.