Dynasearch neighborhood for the earliness-tardiness scheduling problem with release dates and setup constraints

A large dynasearch neighborhood is introduced for the one-machine scheduling problem with sequence-dependent setup times and costs and earliness–tardiness penalties. Finding the best schedule in this neighborhood is NP-complete in the ordinary sense but can be done in pseudo-polynomial time. We also...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 2006-09, Vol.34 (5), p.591-598
Main Author: Sourd, Francis
Format: Article
Language:English
Subjects:
Computer Science
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A large dynasearch neighborhood is introduced for the one-machine scheduling problem with sequence-dependent setup times and costs and earliness–tardiness penalties. Finding the best schedule in this neighborhood is NP-complete in the ordinary sense but can be done in pseudo-polynomial time. We also present experimental results.
ISSN:0167-6377
1872-7468
DOI:10.1016/j.orl.2005.06.005