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

Yacine Laalaoui; Rym M’Hallah

doi:10.1007/s10479-024-06386-7

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

Yacine Laalaoui, Rym M’Hallah^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

This paper presents a new heuristic search 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. 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 F_IR for large-scale instances. In fact, 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.

Original language	English
Journal	Annals of Operations Research
DOIs	https://doi.org/10.1007/s10479-024-06386-7
Publication status	Accepted/In press - 2024

Keywords

Deadlines
F Heuristic search
Incremental Search
Release dates
Restarts
Scheduling

Access to Document

10.1007/s10479-024-06386-7

Cite this

@article{3f09baa7d8984daeae0ab9b903946360,

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

abstract = "This paper presents a new heuristic search FIR 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. FIR uses incremental search and restart strategies to scale the best-first-search heuristic F (Laalaoui and M{\textquoteright}Hallah, in: IEEE symposium on evolutionary scheduling and combinatorial optimisation (SSCI) 2022, IEEE, Singapore, 2022). Experimental results provide computational evidence of the superiority of FIR for large-scale instances. In fact, FIR 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 = "Deadlines, F Heuristic search, Incremental Search, Release dates, Restarts, Scheduling",

author = "Yacine Laalaoui and Rym M{\textquoteright}Hallah",

note = "Publisher Copyright: {\textcopyright} The Author(s) 2024.",

year = "2024",

doi = "10.1007/s10479-024-06386-7",

language = "English",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer",

}

TY - JOUR

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

AU - Laalaoui, Yacine

AU - M’Hallah, Rym

N1 - Publisher Copyright: © The Author(s) 2024.

PY - 2024

Y1 - 2024

N2 - This paper presents a new heuristic search FIR 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. FIR 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 FIR for large-scale instances. In fact, FIR 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.

AB - This paper presents a new heuristic search FIR 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. FIR 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 FIR for large-scale instances. In fact, FIR 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.

KW - Deadlines

KW - F Heuristic search

KW - Incremental Search

KW - Release dates

KW - Restarts

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=85209740253&partnerID=8YFLogxK

U2 - 10.1007/s10479-024-06386-7

DO - 10.1007/s10479-024-06386-7

M3 - Article

AN - SCOPUS:85209740253

SN - 0254-5330

JO - Annals of Operations Research

JF - Annals of Operations Research

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this