NEIGHBORHOOD ALGORITHM FOR FLEXIBLE JOB SHOP SCHEDULING PROBLEMS

The flexible job shop scheduling problem (FJSSP) is an extension of the classical job shop scheduling problem (JSSP), which allocates jobs to resources while minimizing the maximal completion time of the jobs. In FJSSP, machine assignment and job sequence are determined. To efficiently solve FJSSP, which is NP-hard, we require a heuristic method. In previous researches, the FJSSP has been solved by neighborhood algorithms, which employ various meta-heuristic methods. These approaches constrain the neighborhood operation to jobs on a critical path, and simultaneously change the machine assignment and job sequence. However, as branches on the critical path are easily generated in FJSSP search processes, this branch structure could improve the efficiency of FJSSP. This study investigates two neighborhood algorithms for changing machine assignment and job sequence via a critical path. One is the method which changes machine assignment and job sequence simultaneously. Another is the method which changes machine assignment and job sequence independently. Finally, it proposes efficient neighborhood algorithms.