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.
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications