The computational complexity of scheduling jobs with released dates on an unbounded batch processing machine to minimize total completion time and on parallel unbounded batch processing machines to minimize total weighted completion time remains open. In this note we show that the first problem is NP-hard with respect to id-encoding, and the second one is strongly NP-hard.
|Number of pages||4|
|Journal||Computers and Industrial Engineering|
|Publication status||Published - 1 May 2010|
- Batch processing
- Computational complexity
ASJC Scopus subject areas
- Computer Science(all)