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

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

0.00 Avg rating0 Votes
Article ID: iaor1999185
Country: United States
Volume: 45
Issue: 2
Start Page Number: 231
End Page Number: 242
Publication Date: Mar 1998
Journal: Naval Research Logistics
Authors: , ,
Abstract:

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 de Velde, and Veltman. An efficient heuristic is also developed for this case. The relative error of this heuristic is at most 100%.

Reviews

Required fields are marked *. Your email address will not be published.