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.

Statistics

Seen <100 times
0 Comments

More articles like this

Multi-stage ordinal optimization based approach fo...

on Applied Mathematics and Comput... Oct 15, 2012

The complexity of shop-scheduling problems with tw...

on European Journal of Operationa... Jan 01, 1991

A multi-objective PSO for job-shop scheduling prob...

on Expert Systems with Applicatio... Jan 01, 2010

On the complexity and some properties of multi-sta...

on Computers & Operations Researc... Jan 01, 2004
More articles like this..