Fuzzy job-shop scheduling problems: A Review

Abstract

This comprehensive review paper provides a systematic examination of Fuzzy Job-Shop Scheduling Problems (Fuzzy JSSPs), a significant extension of classical scheduling that incorporates uncertainty through fuzzy sets to model imprecise parameters like processing times and due dates. The authors, Abdullah and Abdolrazzagh-Nezhad, consolidate the research published between 1995 and 2013, highlighting that the field is still in its infancy with fewer than 60 dedicated papers at the time of writing. The review is motivated by the need to address real-world scheduling complexities where human factors and unpredictable conditions make crisp time assumptions unrealistic.

The paper begins by classifying Fuzzy JSSPs into three main categories based on the sources of uncertainty: problems with fuzzy due dates, those with fuzzy processing times, and those combining both. Among these, the most frequently studied type (58% of literature) is the one with both fuzzy processing times and due dates, while the least addressed is the model with only fuzzy due dates. The authors further detail eight specific fuzzy models proposed by various researchers, such as Xie’s, Lin’s, Sakawa’s, and Lei’s models, each distinguished by its treatment of fuzzy numbers, objective functions, and constraints. These models formalize how fuzzy parameters are represented, often using triangular or trapezoidal fuzzy numbers, and define objectives like maximizing satisfaction degrees or agreement indices, which measure how well completion times meet fuzzy due dates.

A significant portion of the review is dedicated to the methodologies employed to solve Fuzzy JSSPs. The authors note that exact methods, like branch and bound, are rarely used due to their computational impracticality for large-scale problems. Heuristic methods, such as dispatching rules or Johnson’s algorithm, are simple and fast but limited in effectiveness for complex, multi-machine scenarios. Consequently, the paper identifies meta-heuristic algorithms as the state-of-the-art approach, with Genetic Algorithms (GAs) dominating the landscape, accounting for 61% of the applied improvement algorithms. Other meta-heuristics like Particle Swarm Optimization, Ant Colony Optimization, and Tabu Search are also discussed, though their application is less frequent.

The implementation of meta-heuristics is analyzed in a structured three-step framework: pre-processing (encoding and decoding solutions), initialization (generating initial solutions), and improvement (applying intelligent search techniques). The review reveals that operation-based encoding is the most popular representation, and random initialization is overwhelmingly preferred, despite its potential drawbacks. The authors point out a notable gap: the lack of heuristic initialization procedures that could generate high-quality starting solutions close to optimal, which would significantly speed up convergence. They also emphasize that the diversity of algorithms is unsatisfactory, with many promising meta-heuristics like Electromagnetic-like Mechanism or Variable Neighborhood Search remaining unexplored for Fuzzy JSSPs.

The paper concludes by evaluating benchmark datasets, which are categorized into fuzzy benchmarks (like Sakawa’s datasets) and fuzzed benchmarks derived from crisp instances. It summarizes the advantages and disadvantages of different problem types and methodologies, ultimately arguing that meta-heuristics, despite not guaranteeing optimality, are the most effective for tackling real-world, large-scale Fuzzy JSSPs. The key achievement of this review is the first-time consolidation of scattered literature, providing a clear taxonomy, identifying critical research gaps, and offering a roadmap for future studies to enhance initialization strategies, explore underutilized algorithms, and develop more robust fuzzy scheduling models.