Affordable Access

Publisher Website

Complexity of the job insertion problem in multi-stage scheduling

Authors
Journal
Operations Research Letters
0167-6377
Publisher
Elsevier
Publication Date
Volume
35
Issue
6
Identifiers
DOI: 10.1016/j.orl.2007.02.004
Keywords
  • Scheduling
  • Computational Complexity

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.