Enhancing the best-first-search F with incremental search and restarts for large-scale single machine scheduling with release dates and deadlines

Yacine Laalaoui () and Rym M’Hallah ()
Additional contact information
Yacine Laalaoui: Taif University
Rym M’Hallah: King’s College London

Annals of Operations Research, 2025, vol. 351, issue 1, No 12, 303-332

Abstract: Abstract This paper presents a new heuristic search $$\hbox {F}_{IR}$$ F IR that determines the feasibility of scheduling a set of jobs on a single machine where each job is characterized by its release date, processing time, and deadline. $$\hbox {F}_{IR}$$ F IR uses incremental search and restart strategies to scale the best-first-search heuristic F (Laalaoui and M’Hallah, in: IEEE symposium on evolutionary scheduling and combinatorial optimisation (SSCI) 2022, IEEE, Singapore, 2022). Experimental results provide computational evidence of the superiority of $$\hbox {F}_{IR}$$ F IR for large-scale instances. In fact, $$\hbox {F}_{IR}$$ F IR outperforms the IBM ILOG CP constraint programming solver, the CPLEX mixed integer programming solver, and existing heuristics. It finds feasible solutions for many instances with 100,000 jobs in less than one minute.

Keywords: Scheduling; F Heuristic search; Release dates; Deadlines; Restarts; Incremental Search (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-06386-7 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:annopr:v:351:y:2025:i:1:d:10.1007_s10479-024-06386-7

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

DOI: 10.1007/s10479-024-06386-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

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