Improved heuristics for the single machine scheduling problem with linear early and quadratic tardy penalties

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

Authors

Jorge M S Valente (Author) FEP; Jeffrey E Schaller (Author) Other

Journal

Title: European Journal of Industrial Engineering

Vol. 4

Pages: 99-129

ISSN: 1751-5254

Publisher: Inderscience Publishers

Indexing

ISI Web of Knowledge - 20 Citations

ISI Web of Science

Scopus - 21 Citations

Scientific classification

FOS: Engineering and technology > Civil engineering

CORDIS: Social sciences > Economics > Management studies

Other information

Authenticus ID: P-003-ATD

DOI: 10.1504/ejie.2010.029572

Abstract (EN): This paper considers the single machine scheduling problem with linear earliness and quadratic tardiness costs. The research on the version with an inserted idle time focused on an exact approach, while several heuristics were already proposed for the version with no idle time. These heuristics were then the basis for the development of new heuristic procedures for the version with idle time. Some improvement procedures were also considered. The new heuristics outperformed the existing procedures. A genetic algorithm provides the best results in terms Of Solution quality, but is computationally intensive. One of the backward scheduling dispatching rules provides results of similar quality and can quickly solve even large instances. The new heuristics were also applied, with the appropriate modifications, to the version with no idle time. Again, the new procedures provided better results than the existing heuristics. Therefore, the procedures developed in this paper are the new heuristics of choice for both versions of the considered problem. [Received 09 October 2008; Revised 02 February 2009; Accepted 20 February 2009]

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 31