A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time

A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time

0.00 Avg rating0 Votes
Article ID: iaor2005503
Country: United Kingdom
Volume: 31
Issue: 10
Start Page Number: 1727
End Page Number: 1751
Publication Date: Sep 2004
Journal: Computers and Operations Research
Authors: , ,
Keywords: programming: branch and bound
Abstract:

The single-machine early/tardy scheduling problem is addressed in this research. The objective of this problem is to minimize the total amount of earliness and tardiness. Earliness and tardiness are weighted equally and the due date is common and large (unrestricted) for all jobs. Machine setup time is included and is considered sequence-dependent. When sequence-dependent setup times are included, the complexity of the problem increases significantly and the problem becomes NP-hard. In the literature, only mixed integer programming formulation is available to optimally solve the problem at hand. In this paper, a branch-and-bound algorithm (B&B) is developed to obtain optimal solutions for the problem. As it will be shown, the B&B solved problems three times larger than what has been reported in the literature.

Reviews

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