A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines

The purpose of this paper is to propose a new branch-and-bound algorithm for a class of scheduling problems to minimize total tardiness on identical parallel machines. In this algorithm, the Lagrangian relaxation technique is applied to obtain a tight lower bound. In addition, the job dominance cond...

Full description

Saved in:
Bibliographic Details
Published in:International journal of production economics 2008-05, Vol.113 (1), p.446-458
Main Authors: Tanaka, Shunji, Araki, Mituhiko
Format: Article
Language:English
Subjects:
Algorithms
Branch & bound algorithms
Branch-and-bound algorithm
Identical parallel machines
Lagrange multiplier
Lagrangian relaxation
Problem solving
Production scheduling
Scheduling
Studies
Total 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 purpose of this paper is to propose a new branch-and-bound algorithm for a class of scheduling problems to minimize total tardiness on identical parallel machines. In this algorithm, the Lagrangian relaxation technique is applied to obtain a tight lower bound. In addition, the job dominance conditions for the single machine total tardiness problem are utilized for both restricting branches and improving the lower bound. As will be shown by computational experiments, instances with up to 25 jobs and with any number of machines are optimally solved by the proposed algorithm.
ISSN:0925-5273
1873-7579
DOI:10.1016/j.ijpe.2007.10.006