A branch and bound to minimize the number of late jobs on a single machine with release time constraints

A branch and bound to minimize the number of late jobs on a single machine with release time constraints

0.00 Avg rating0 Votes
Article ID: iaor20042041
Country: Netherlands
Volume: 144
Issue: 1
Start Page Number: 1
End Page Number: 11
Publication Date: Jan 2003
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: branch and bound
Abstract:

This paper presents a branch and bound algorithm for the single machine scheduling problem 1|ri|∑Ui where the objective function is to minimize the number of late jobs. Lower bounds based on a Lagrangian relaxation and no reductions to polynomially solvable cases are proposed. Efficient elimination rules together with strong dominance relations are also used to reduce the search space. A branch and bound exploiting these techniques solves to optimality instances with up to 200 jobs, improving drastically the size of problems that could be solved by exact methods up to now.

Reviews

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