A Benchmarking Suite for Flexible Job Shop Scheduling Problems with Worker Flexibility under Uncertainty

Technical Summary: A Benchmarking Suite for Flexible Job Shop Scheduling Problems with Worker Flexibility under Uncertainty

Problem Definition
The paper addresses the Flexible Job Shop Scheduling Problem (FJSSP) and its extension, the Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W). While the classical FJSSP involves assigning operations to eligible machines to minimize a cost function (typically makespan), the FJSSP-W further integrates workforce assignment. In this extended problem, an operation must be assigned not only to a specific machine but also to an eligible worker, where the specific machine-worker combination determines the processing time.

A significant gap identified in the literature is the lack of a standardized, systematic benchmarking environment for these problems, particularly when incorporating uncertainty (e.g., stochastic processing times, machine breakdowns, and worker unavailability). Existing research often relies on fragmented, ad-hoc instance sets or specific real-world cases that hinder cross-domain comparison between solvers from different optimization paradigms (Mathematical Programming, Constraint Programming, and Simulation-Based Optimization).

Methodology and Benchmark Construction
The authors propose a comprehensive, open-source benchmarking suite implemented in Python. The methodology involves three primary components:

1. Instance Collection and Extension:

   • The suite is built upon a curated collection of 402 distinct FJSSP instances drawn from ten established sources (e.g., Brandimarte, Hurink, Kacem).
   • These instances are systematically extended to create FJSSP-W instances. The extension process assigns a set of workers ($W$) to each operation-machine combination.
   • Worker Assignment Logic: For each operation-machine pair, a random number of eligible workers is sampled. Processing times for these new combinations are generated by sampling from a distribution centered around the original machine processing time (default range: 90% to 110% of the base time).
   • Characterization: The suite documents specific instance characteristics, including the number of jobs ($n$), machines ($m$), workers ($w$), operations ($N$), flexibility ($\beta$), and duration variety ($d_v$), allowing for feature-based filtering.

2. Uncertainty Modeling via Discrete-Event Simulation (DES):

   • The environment supports the simulation of three types of uncertainty: processing time variability, machine breakdowns, and worker unavailability.
   • Processing Times: Modeled using Beta distributions to simulate inconsistent working speeds.
   • Machine Breakdowns: Modeled using Exponential distributions for occurrence (averaging one breakdown per schedule) and Weibull distributions for duration (minimum 10% of the noise-free makespan).
   • Worker Unavailability: Also modeled with Exponential (lower frequency) and Weibull (longer duration, minimum 50% of noise-free makespan) distributions.
   • Solutions are represented as Directed Acyclic Graphs (DAGs) to facilitate traversal and simulation of these stochastic events.

3. Evaluation Framework:

   • The suite provides APIs for loading instances, translating encodings (e.g., between FJSSP and FJSSP-W), and evaluating performance.
   • Metrics: The primary objective is minimizing makespan. For uncertainty simulations, the robust makespan ($C_r$) is calculated as the average actual makespan over multiple simulation runs.
   • Statistical Analysis: The framework includes tools for statistical ranking (Friedman and Nemenyi tests) and visualization (e.g., Nemenyi diagrams) to compare solver performance rigorously.

Key Contributions

• Standardized Benchmark Collection: The creation of a fixed portfolio of 402 FJSSP-W instances, ensuring reproducibility and comparability across studies.
• Open-Source Suite: A Python-based environment that supports multiple optimization paradigms (MILP, CP, Evolutionary Algorithms) by providing necessary model representations and evaluation functions.
• Uncertainty Integration: A systematic method for injecting stochasticity into problem instances, enabling the development and assessment of robust optimization strategies.
• Baseline Results: Provision of "best-known" results derived from state-of-the-art solvers (Gurobi, IBM CPLEX/OR-Tools, and Genetic Algorithms) under a standardized time limit (20 minutes) and hardware configuration.

Experimental Results
The authors demonstrated the suite by comparing four solvers on the 402 FJSSP-W instances:

• Constraint Programming (CP): Significantly outperformed other approaches, achieving a relative deviation ($\delta_{rel}$) of less than 0.25 on over 80% of instances.
• Genetic Algorithm (GA): Performed well, significantly outperforming MILP and Greedy approaches, though trailing CP.
• Mixed-Integer Linear Programming (MILP): Struggled with the scale of the problem; many instances could not be solved within the time limit due to memory constraints and variable counts.
• Greedy Algorithm: Served as a baseline, performing the worst.

In robustness simulations (using the Fattahi20 instance), the framework successfully visualized the degradation of schedules under uncertainty, calculating the robust makespan and the robustness quotient ($R$) to evaluate schedule stability.

Significance and Claims
The paper claims that this work lays a foundation for targeted algorithm development and consistent performance evaluation in production scheduling research. By addressing the fragmentation in current benchmarking practices, the suite enables:

• Fair Comparison: Rigorous, reproducible evaluation across different solvers and problem subdomains.
• Algorithm Development: Support for developing operators for specific problem groups through instance filtering.
• Robustness Assessment: The ability to evaluate how solvers handle real-world uncertainties, moving beyond deterministic optimization.

The authors emphasize that while the suite is designed primarily for Simulation-Based Optimization (SBO) and Evolutionary Algorithms, its provision of model representations for MILP and CP allows for cross-paradigm comparison. They advocate for the use of the fixed instance set to ensure scientific reproducibility and call for transparency in reporting experimental parameters and hardware specifications to facilitate future research.