Title

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

Authors

Authors

G. Rabadi; M. Mollaghasemi;G. C. Anagnostopoulos

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Comput. Oper. Res.

Keywords

single-machine scheduling; earliness/tardiness; early/tardy; sequence-dependent setup times; common due date; branch-and-bound; SINGLE-MACHINE; COMPLETION TIMES; TARDINESS PENALTIES; ABSOLUTE; DEVIATION; EARLINESS; Computer Science, Interdisciplinary Applications; Engineering, ; Industrial; Operations Research & Management Science

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. (C) 2003 Elsevier Ltd. All rights reserved.

Journal Title

Computers & Operations Research

Volume

31

Issue/Number

10

Publication Date

1-1-2004

Document Type

Article

Language

English

First Page

1727

Last Page

1751

WOS Identifier

WOS:000220640500010

ISSN

0305-0548

Share

COinS