Scheduling groups of unit length jobs on two identical parallel machines

Zhaohui Liu, Wenci Yu, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)


The problem of scheduling groups of unit length jobs with group sub-lotting on two identical parallel machines to minimize the total completion time is known to be NP-hard. In this paper, we present a pseudopolynomial-time algorithm for the problem, thus establishing that the problem is NP-hard in the ordinary sense. We also show that the problem remains NP-hard even for the case with any fixed positive set-up time.
Original languageEnglish
Pages (from-to)275-281
Number of pages7
JournalInformation Processing Letters
Issue number6
Publication statusPublished - 26 Mar 1999

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this