A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem

This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2008-02, Vol.11 (1), p.49-58
Main Authors: Sourd, Francis, Kedad-Sidhoum, Safia
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Branch & bound algorithms
Business and Management
Calculus of Variations and Optimal Control
Optimization
Computer Science
Employment
Fines & penalties
Heuristic
Machinery
Operations research
Operations Research/Decision Theory
Optimization
Production scheduling
Scheduling
Studies
Supply Chain Management
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:This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules.
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-007-0048-2