2025/04/17 by Marc-Emmanuel Coupvent des Graviers, Lotfi Kobrosly, Graviers, Marc-Emmanuel Coupvent des +5 · 1 citation
Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #I.2.8 #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2504.16106
openalex publication_date 2025/04/17 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28
The Job-Shop Scheduling Problem (JSSP) and its variant, the Flexible Job-Shop Scheduling Problem (FJSSP), are combinatorial optimization problems studied thoroughly in the literature. Generally, the aim is to reduce the makespan of a scheduling solution corresponding to a problem instance. Thus, finding upper and lower bounds for an optimal makespan enables the assessment of performances for multiple approaches addressed so far. We use OR-Tools, a solver portfolio, to compute new bounds for some open benchmark instances, in order to reduce the gap between upper and lower bounds. We find new numerical lower bounds for multiple benchmark instances, up to closing the Taillard's ta33 instance. We also improve upper bounds for four instances, namely Taillard's ta26 & ta45 and Dauzere's 05a & 06a. Additionally we share an optimal solution for Taillard's ta45 as well as Hurink-edata's car5.