Scatter search for minimizing weighted tardiness in a single machine scheduling with setups

Miguel A. González (), Juan José Palacios (), Camino R. Vela () and Alejandro Hernández-Arauzo ()
Additional contact information
Miguel A. González: University of Oviedo
Juan José Palacios: University of Oviedo
Camino R. Vela: University of Oviedo
Alejandro Hernández-Arauzo: University of Oviedo

Journal of Heuristics, 2017, vol. 23, issue 2, No 1, 110 pages

Abstract: Abstract Single machine scheduling problems have many real-life applications and may be hard to solve due to the particular characteristics of some production environments. In this paper, we tackle the single machine scheduling problem with sequence-dependent setup times with the objective of minimizing the weighted tardiness. To solve this problem, we propose a scatter search algorithm which uses path relinking in its core. This algorithm is enhanced with some procedures to speed-up the neighbors’ evaluation and with some diversification and intensification techniques, the latter taking some elements from iterated local search. We conducted an experimental study across a well-known set of instances to analyze the contribution of each component to the overall performance of the algorithm, as well as to compare our proposal with the state-of-the-art metaheuristics, obtaining competitive results. We also propose a new benchmark with larger and more challenging instances and provide the first results for them.

Keywords: Scheduling; Single machine; Weighted tardiness; Scatter search; Path relinking (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-017-9325-1 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:joheur:v:23:y:2017:i:2:d:10.1007_s10732-017-9325-1

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

DOI: 10.1007/s10732-017-9325-1

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

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