An exact approach for the single machine scheduling problem with linear early and quadratic tardy penalties

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

Authors

Jorge M S Valente (Author) FEP

Journal

Title: Asia-Pacific Journal of Operational Research

Vol. 25 No. 2

Pages: 169-186

ISSN: 0217-5959

Publisher: World Scientific

Indexing

ISI Web of Knowledge - 12 Citations

ISI Web of Science

Scopus - 14 Citations

Scientific classification

FOS: Engineering and technology > Industrial biotechnology

CORDIS: Social sciences > Economics > Management studies

Other information

Authenticus ID: P-004-099

DOI: 10.1142/s0217595908001730

Abstract (EN): In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. We propose a lower bounding procedure based on the relaxation of the jobs' completion times. Optimal branch-and-bound algorithms are then presented. These algorithms incorporate the proposed lower bound, as well as an insertion-based dominance test. The branch-and-bound procedures are tested on a wide set of randomly generated problems. The computational results show that the branch-and-bound algorithms are capable of optimally solving, within reasonable computation times, instances with up to 20 jobs.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18