Heuristic methods for the single machine scheduling problem with different ready times and a common due date

The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constr...

Full description

Saved in:
Bibliographic Details
Published in:Engineering optimization 2012-10, Vol.44 (10), p.1197-1208
Main Authors: Birgin, Ernesto G., Ronconi, Débora P.
Format: Article
Language:English
Subjects:
Benchmarking
Benchmarks
Computation
Construction specifications
Due dates
earliness
Heuristic
heuristic methods
Minimization
Optimization
Performance evaluation
Scheduling
single machine
tardiness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance is investigated. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs.
ISSN:0305-215X
1029-0273
DOI:10.1080/0305215X.2011.634409