Solving the Flexible Job Shop Scheduling Problem with Alternative Process Plans

Abstract

This thesis addresses the Flexible Job Shop Scheduling Problem (FJSP) with three extensions: Sequence-Dependent Setup Times (SDST), Blocking tasks and Alternative Process Plans (APPs). The research evaluates the efficacy of two optimization paradigms: Constraint Programming (CP) and Multivalued Decision Diagrams (MDDs). For CP, both the commercial IBM CPLEX CP Optimizer and Google’s open-source OR-Tools CP-SAT solver are utilized. The study formalizes the problem, including multifunctional machine routing, SDST, blocking constraints, and APPs, into a unified CP model, demonstrating its robust framework for realtime, make-to-order environments. Both solvers are competitive, with either having a slight advantage in certain aspects. Furthermore, it explores MDDs as a complementary technique, showcasing how restricted and relaxed MDD variants can quickly generate bounds and decent solutions. Through extensive computational experiments on both established and newly generated benchmark instances (the latter made publicly available), this thesis shows that alternative process plans can directly be implemented to try and minimize setup times and establishes hybrid CP-MDD strategies as a promising direction for large-scale, real-time scheduling implementations in high-mix, low-volume production settings. The findings indicate that while CP offers greater flexibility and gradually improves solutions over longer runtimes, MDDs excel in quickly generating decent schedules, particularly when SDST are involved, making them suitable for scenarios prioritizing rapid schedule creation.