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

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

0.00 Avg rating0 Votes
Article ID: iaor20002060
Country: United Kingdom
Volume: 26
Issue: 7
Start Page Number: 679
End Page Number: 693
Publication Date: Jun 1999
Journal: Computers and Operations Research
Authors:
Keywords: programming: branch and bound, heuristics, lagrange multipliers
Abstract:

This paper addresses the problem of scheduling a given set of independent jobs on a single machine to minimize the sum of weighted earliness and weighted tardiness without considering machine idle time. Efficient lower and upper bounds are developed. The lower bound is obtained based on a Lagrangian relaxation that decomposes the problem into two subproblems, and an efficient lower bounding procedure for each of the subproblems. The upper bound is obtained using a two-phase heuristic procedure that combines a priority dispatching rule with a local improvement procedure. A branch-and-bound algorithm incorporating these bounds and some dominance rules is proposed. Computational experiments on problems with up to 50 jobs show that both the lower and upper bounds are very tight and the branch-and-bound algorithm performs very well.

Reviews

Required fields are marked *. Your email address will not be published.