A Global Neighborhood with Hill-Climbing Algorithm for Fuzzy Flexible Job Shop Scheduling Problem

Abstract

The Flexible Job Shop Scheduling Problem (FJSSP) continues to be studied extensively to test new metaheuristics and because of its closeness to current production systems. A variant of the FJSSP uses fuzzy processing times instead of fixed times. This paper proposes a new algorithm for FJSSP with fuzzy processing times called the global neighborhood with hill-climbing algorithm (GN-HC). This algorithm performs solution exploration using simple operators concurrently for global search neighborhood handling. For local search, random restart hill-climbing is applied at each solution to find the best machine for each operation. For the selection of operations in hill climbing, a record of the operations defining the fuzzy makespan is employed to use them as a critical path. Finally, an estimation of the crisp makespan with the longest processing times in hill climbing is made to improve the speed of the GN-HC. The GN-HC is compared with other recently proposed methods recognized for their excellent performance, using 6 FJSSP instances with fuzzy times. The obtained results show satisfactory competitiveness for GN-HC compared to state-of-the-art algorithms. The GN-HC implementation was performed in Matlab and can be found on GitHub (check Data Availability Statement at the end of the paper).

Keywords

• job shop scheduling
• fuzzy processing times
• global search
• hill climbing
• critical path