An exact approach to early/tardy scheduling with release dates

• Type: Article in International Scientific Journal
• Date: 2005

Authors

Valente, JMS (Author) FEP; Alves, RAFS (Author) FEP

Journal

Title: Computers and Operations Research

Vol. 32

Pages: 2905-2917

ISSN: 0305-0548

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 30 Citations

ISI Web of Science

Scopus - 37 Citations

Scientific classification

FOS: Engineering and technology > Civil engineering

CORDIS: Social sciences > Economics > Management studies

Other information

Authenticus ID: P-000-0KZ

DOI: 10.1016/j.cor.2004.04.016

Abstract (EN): In this paper, we consider the single machine earliness/tardiness scheduling problem with different release dates and no unforced idle time. The problem is decomposed into weighted earliness and weighted tardiness subproblems. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is the sum of the lower bounds for the two subproblems. The lower bounds and several version, of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13