\textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees

DOI10.1016/j.cor.2020.105171OpenAlexW3120141628MaRDI QIDQ2027052

Vincent T'kindt, Lei Shang, Frederico Della Croce

Publication date: 21 May 2021

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2020.105171

zbMATH Keywords

schedulingsequencingexact algorithmsmemorizationbranch and memorize

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Related Items (3)

Single machine rescheduling for new orders with maximum lateness minimization ⋮ Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness ⋮ Moderate exponential-time algorithms for scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generalized resolution search
• A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates
• Exact exponential algorithms.
• Resolution search
• A faster branch-and-bound algorithm for the earliness-tardiness scheduling problem
• A branch, bound, and remember algorithm for the \(1|r _{i }|\sum t _{i }\) scheduling problem
• The single-machine total tardiness scheduling problem: review and extensions
• The one-machine sequencing problem
• An algorithm for single machine sequencing with deadlines to minimize total weighted completion time
• Scheduling around a small common due date
• Solution of the single machine total tardiness problem
• Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
• An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
• Resolution search and dynamic branch-and-bound
• A decomposition algorithm for the single machine total tardiness problem
• Exact algorithms for maximum independent set
• An exact algorithm for single-machine scheduling without machine idle time
• An application of the branch, bound, and remember algorithm to a new simple assembly line balancing dataset
• Exact algorithms for maximum induced matching
• A dynamic-programming-based exact algorithm for general single-machine scheduling with machine idle time
• Revisiting branch and bound search strategies for machine scheduling problems
• A Branch, Bound, and Remember Algorithm for the Simple Assembly Line Balancing Problem
• Minimizing Total Tardiness on One Machine is NP-Hard
• Minimizing Weighted Completion Times with Deadlines
• Algorithms for maximum independent sets
• Expected Computation Time for Hamiltonian Path problem
• Tabu Search—Part I
• Tabu Search—Part II
• One-Machine Sequencing to Minimize Certain Functions of Job Tardiness
• Algorithmic paradoxes of the single-machine total tardiness problem

This page was built for publication: \textit{Branch} \& \textit{Memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees