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

Xiaoqiang Cai, Chung Yee Lee, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

20 Citations (Scopus)


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%.
Original languageEnglish
Pages (from-to)231-242
Number of pages12
JournalNaval Research Logistics
Issue number2
Publication statusPublished - 1 Jan 1998
Externally publishedYes


  • Computational complexity
  • Multiprocessor tasks
  • Scheduling
  • Worst-case analysis

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Cite this