Print Email Facebook Twitter Combinatorial optimization for job sequencing with one common and multiple secondary resources by using a SAT solver augmented with a domain-specific heuristic Title Combinatorial optimization for job sequencing with one common and multiple secondary resources by using a SAT solver augmented with a domain-specific heuristic Author Pugatšov, Artjom (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Demirović, E. (mentor) Sidorov, K. (mentor) Flippo, M.L. (mentor) Decouchant, Jérémie (graduation committee) Degree granting institution Delft University of Technology Programme Computer Science and Engineering Project CSE3000 Research Project Date 2023-07-04 Abstract This paper solves job sequencing with one common and multiple secondary resources (JSOCMSR) problem by encoding it as a Boolean satisfiability (SAT) problem and applying domain-specific heuristics to improve the SAT solver’s performance. JSOCMSR problem is an NP-hard scheduling problem where each job utilizes two resources: a shared resource and a secondary job-dependent resource. First, the problem was modeled as an instance of SAT and then the SAT solver was augmented with a static greedy variable-ordering heuristic. This heuristic has led to significant improvement in the solver’s speed compared to a generic SAT heuristic for problem instances of larger size. Subject JSOCMSRSATSchedulingHeuristicSAT solver To reference this document use: http://resolver.tudelft.nl/uuid:835629e5-57fc-4cd0-ba40-68edb63bf58b Part of collection Student theses Document type bachelor thesis Rights © 2023 Artjom Pugatšov Files PDF CSE3000_Final_Paper_A_Pugatsov.pdf 353.03 KB Close viewer /islandora/object/uuid:835629e5-57fc-4cd0-ba40-68edb63bf58b/datastream/OBJ/view