A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems

Arthur Kramer () and Anand Subramanian ()
Additional contact information
Arthur Kramer: Universidade Federal da Paraíba
Anand Subramanian: Universidade Federal da Paraíba

Journal of Scheduling, 2019, vol. 22, issue 1, No 3, 57 pages

Abstract: Abstract This work proposes a unified heuristic algorithm for a large class of earliness–tardiness (E–T) scheduling problems. We consider single/parallel machine E–T problems that may or may not consider some additional features such as idle time, setup times and release dates. In addition, we also consider those problems whose objective is to minimize either the total (average) weighted completion time or the total (average) weighted flow time, which arise as particular cases when the due dates of all jobs are either set to zero or to their associated release dates, respectively. The developed local search-based metaheuristic framework is quite simple, but at the same time relies on sophisticated procedures for efficiently performing local search according to the characteristics of the problem. We present efficient move evaluation approaches for some parallel machine problems that generalize the existing ones for single machine problems. The algorithm was tested in thousands of instances of several E–T problems and particular cases. The results obtained show that our unified heuristic is capable of producing high-quality solutions when compared to the best ones available in the literature that were obtained by specific methods. Moreover, we provide an extensive annotated bibliography on the problems related to those considered in this work, where we not only indicate the approach(es) used in each publication, but we also point out the characteristics of the problem(s) considered. Beyond that, we classify the existing methods in different categories so as to have a better idea of the popularity of each type of solution procedure.

Keywords: Earliness–tardiness; Heuristic framework; Iterated Local Search; Survey (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-017-0549-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:22:y:2019:i:1:d:10.1007_s10951-017-0549-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-017-0549-6

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().