Iterated local search for single machine total weighted tardiness batch scheduling

Eduardo Queiroga (), Rian G. S. Pinheiro (), Quentin Christ (), Anand Subramanian () and Artur A. Pessoa ()
Additional contact information
Eduardo Queiroga: Universidade Federal Fluminense
Rian G. S. Pinheiro: Universidade Federal de Alagoas
Quentin Christ: Ecole des Mines de Saint-Etienne, CNRS UMR 6158 LIMOS
Anand Subramanian: Universidade Federal da Paraíba
Artur A. Pessoa: Universidade Federal Fluminense

Journal of Heuristics, 2021, vol. 27, issue 3, No 4, 353-438

Abstract: Abstract This paper presents an iterated local search (ILS) algorithm for the single machine total weighted tardiness batch scheduling problem. To our knowledge, this is one of the first attempts to apply ILS to solve a batching scheduling problem. The proposed algorithm contains a local search procedure that explores five neighborhood structures, and we show how to efficiently implement them. Moreover, we compare the performance of our algorithm with dynamic programming-based implementations for the problem, including one from the literature and two other ones inspired in biased random-key genetic algorithms and ILS. We also demonstrate that finding the optimal batching for the problem given a fixed sequence of jobs is $$\mathcal {NP}$$ NP -hard, and provide an exact pseudo-polynomial time dynamic programming algorithm for solving such problem. Extensive computational experiments were conducted on newly proposed benchmark instances, and the results indicate that our algorithm yields highly competitive results when compared to other strategies. Finally, it was also observed that the methods that rely on dynamic programming tend to be time-consuming, even for small size instances.

Keywords: Batch scheduling; Total weighted tardiness; Iterated local search; Metaheuristics (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-020-09461-x 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:27:y:2021:i:3:d:10.1007_s10732-020-09461-x

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

DOI: 10.1007/s10732-020-09461-x

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 ().