Complexity of the job insertion problem in multi-stage scheduling

A.P.A. Vestjens, M. Wennink, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

The job insertion problem in multi-stage scheduling is: given a schedule for n jobs and an additional job, find a feasible insertion of the additional job into the schedule that minimizes the resulting makespan. We prove that finding the optimal job insertion is NP-hard for flow shops and open shops.
Original languageEnglish
Pages (from-to)754-758
JournalOperations Research Letters
Volume35
Issue number6
DOIs
Publication statusPublished - 2007

Fingerprint

Dive into the research topics of 'Complexity of the job insertion problem in multi-stage scheduling'. Together they form a unique fingerprint.

Cite this