Solving the Flexible Job Shop Scheduling Problem with Alternative Process Plans
Summary
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.