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

Xiaoqiang Cai, Chung‐Yee Lee and Chung‐Lun Li

Naval Research Logistics (NRL), 1998, vol. 45, issue 2, 231-242

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 (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

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199803)45:23.0.CO;2-9

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:45:y:1998:i:2:p:231-242

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().