Title

A Branch-And-Bound Algorithm For The Early/Tardy Machine Scheduling Problem With A Common Due-Date And Sequence-Dependent Setup Time

Keywords

Branch-and-bound; Common due date; Earliness/tardiness; Early/tardy; Sequence-dependent setup times; Single-machine scheduling

Abstract

The single-machine early/tardy (E/T) 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. © 2003 Elsevier Ltd. All rights reserved.

Publication Date

9-1-2004

Publication Title

Computers and Operations Research

Volume

31

Issue

10

Number of Pages

1727-1751

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/S0305-0548(03)00117-5

Socpus ID

1842762099 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/1842762099

This document is currently not available here.

Share

COinS