Optimization Algorithm for Flexible Job-Shop Scheduling Problem Based on Heuristic Rules and Adjustment of Critical Paths

In order to overcome the disadvantages of long computing time and unstable result of traditional evolutionary algorithms in solving the optimization for large flexible job-shop problems (FJSPs), a heuristic critical path approach (HCPA) was proposed. This method first uses a heuristic rule to get some preliminary schedules. Then, critical workpieces and key process of these preliminary schedules are searched and critical paths are locally adjusted using some heuristic rules for better solutions. Finally, the optimal schedule of FJSP is obtained by comparison among these solutions. The proposed approach was applied to benchmark FJSPs, and the solutions were compared with those of other approaches. The results show that for the 1510 FJSP, the values of evaluation indexes computed by the proposed method are nearly the same as those by the integrated genetic algorithm, but the computing time (only 3.2 s) is reduced by 42%. The large FJSPs of 2310 and 2510 are also calculated, reflecting that introduction of heuristic rules can improve the computing efficiency and solution stability; compared with the traditional evolutionary algorithms, the proposed method is more suitable for real-time solution of difficult FJSPs.