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

This paper presents a new heuristic search <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext>F</mml:mtext> <mml:mrow><mml:mi>IR</mml:mi></mml:mrow> </mml:msub> </mml:math> 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. <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext>F</mml:mtext> <mml:mrow><mml:mi>IR</mml:mi></mml:mrow> </mml:msub> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext>F</mml:mtext> <mml:mrow><mml:mi>IR</mml:mi></mml:mrow> </mml:msub> </mml:math> for large-scale instances. In fact, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mtext>F</mml:mtext> <mml:mrow><mml:mi>IR</mml:mi></mml:mrow> </mml:msub> </mml:math> 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.