MINIMIZING TOTAL COMPLETION-TIME IN 2-PROCESSOR TASK SYSTEMS WITH PRESPECIFIED PROCESSOR ALLOCATIONS

Authors
CAI XQ LEE CY LI CL
Citation
Xq. Cai et al., MINIMIZING TOTAL COMPLETION-TIME IN 2-PROCESSOR TASK SYSTEMS WITH PRESPECIFIED PROCESSOR ALLOCATIONS, Naval research logistics, 45(2), 1998, pp. 231-242
Citations number
17
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science","Engineering, Marine
Journal title
Naval research logistics → ACNP
ISSN journal
0894069X
Volume
45
Issue
2
Year of publication
1998
Pages
231 - 242
Database
ISI
SICI code
0894-069X(1998)45:2<231:MTCI2T>2.0.ZU;2-5
Abstract
We consider the problem of scheduling multiprocessor tasks with prespe cified processor allocations to minimize the total completion time. Th e complexity of both preemptive and nonpreemptive cases of the two-pro cessor problem are studied. We show that the preemptive case is solvab le in O(n log n) time. In the nonpreemptive case, we prove that the pr oblem is NP-hard in the strong sense, which answers an open question m entioned in Hoogeveen, van de Velde, and Veltman (1994). An efficient heuristic is also developed for this case. The relative error of this heuristic is at most 100%. (C) 1998 John Wiley & Sons, Inc.