Premium
Minimizing total completion time in two‐processor task systems with prespecified processor allocations
Author(s) -
Cai Xiaoqiang,
Lee ChungYee,
Li ChungLun
Publication year - 1998
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199803)45:2<231::aid-nav7>3.0.co;2-9
Subject(s) - multiprocessing , computer science , heuristic , task (project management) , scheduling (production processes) , execution time , mathematical optimization , parallel computing , mathematics , artificial intelligence , management , economics
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 (1994). An efficient heuristic is also developed for this case. The relative error of this heuristic is at most 100%. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 231–242, 1998