A comparison of lower bounds for the single-machine early/tardy problem

A comparison of lower bounds for the single-machine early/tardy problem

0.00 Avg rating0 Votes
Article ID: iaor20083022
Country: United Kingdom
Volume: 34
Issue: 8
Start Page Number: 2279
End Page Number: 2292
Publication Date: Aug 2007
Journal: Computers and Operations Research
Authors:
Keywords: programming: branch and bound
Abstract:

This paper considers the single-machine early/tardy problem. The paper presents a procedure that integrates a timetabling algorithm into a lower bound for jobs not included in a partial sequence. The paper also shows how two lower bounds that were developed previously for the problem can be improved. The lower bounds are tested on problems of various sizes and parameters for the distribution of due dates. The results show that the lower bounds are able to increase the efficiency of a branch-and-bound algorithm.

Reviews

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