The flexible job shop scheduling problem (FJSSP) is an extension of the classical job shop scheduling problem (JSSP) that allocates jobs to resources while minimizing the maximum completion time of all the jobs. Machine assignment and job sequence are determined in the FJSSP. To efficiently solve the FJSSP, which is a non-deterministic polynomial-time hard problem, a heuristic method must be used. In previous studies, the FJSSP has been solved using neighborhood algorithms that employ various metaheuristic methods. These approaches constrain the neighborhood operation to jobs on a critical path and simultaneously change the machine assignment and job sequence. Branches on the critical path are easily generated in the FJSSP search processes; this branch structure can improve the efficiency of the FJSSP. This study investigates two neighborhood search algorithms used for changing the machine assignment and job sequence via a critical path. The first method changes the machine assignment and job sequence simultaneously, whereas the second method changes them independently. In this study, we propose an efficient neighborhood generating method using a branch block of critical path.

1. [1] J. A. Buzacott and D. D. Yao, “Flexible manufacturing systems: a review of analytical models,” Management Science, Vol.32, No.7, pp. 890-905, 1986.
2. [2] M. R. Garey, D. S. Johnson, and R. Sethi, “The complexity of flowshop and jobshop scheduling,” Mathematics of Operations Research, Vol.1, No.2, pp. 117-129, 1976.
3. [3] J. F. Muth and G. L. Thompson, “Industrial Scheduling,” Prentice-Hall, 1963.
4. [4] J. Blazewicz, K. L. Ecker, G. Schmidt, and J. Weglarz, “Scheduling in Computer and Manufacturing Systems,” Springer-Verlag, 1994.
5. [5] P. Brucker, B. Jurisch, and B. Sievers, “A branch and bound algorithm for the job-shop scheduling problem,” Discrete Applied Mathematics, Vol.49, No.1-3, pp. 107-127, 1994.
6. [6] Y. Sudo and M. Matsuda, “Autonomous Assembly Process Planning According to the Production Line Configuration,” Int. J. Automation Technol., Vol.9, No.3, pp. 261-269, 2015.
7. [7] J. Y. Chai, T. Sakaguchi, and K. Shirase, “Dynamic Controls of Genetic Algorithm Scheduling in Supply Chain,” Int. J. Automation Technol., Vol.4, No.2, pp. 169-177, 2010.
8. [8] S. Dauzère-Pérès and J. Paulli, “An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search,” Annals of Operations Research, Vol.70, No.0, pp. 281-306, 1997.
9. [9] P. Brandimarte, “Routing and scheduling in a flexible job shop by tabu search,” Annals of Operations Research, Vol.41, No.3, pp. 157-183, 1993.
10. [10] J. Gao, L. Sun, and M. Gen, “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems,” Computers & Operations Research, Vol.35, No.9, pp. 2892-2907, 2008.
11. [11] S. Yokoyama, H. Iizuka, and M. Yamamoto, “Priority Rule-Based Construction Procedure Combined with Genetic Algorithm for Flexible Job-Shop Scheduling Problem,” J. Adv. Comput. Intell. Intell. Inform., Vol.19, No.6, pp. 892-899, 2015.
12. [12] J.-Q. Li, Q.-K. Pan, P. N. Suganthan, and T. J. Chua, “A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem,” Int. J. of Advanced Manufacturing Technology, Vol.52, No.5-8, pp. 683-697, 2011.
13. [13] J.-Q. Li, Q.-K. Pan, and K.-Z. Gao, “Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems,” Int. J. of Advanced Manufacturing Technology, Vol.55, No.9-12, pp. 1159-1169, 2011.
14. [14] M. Mastrolilli and L. M. Gambardella, “Effective neighborhood functions for the flexible job shop problem,” J. of Scheduling, Vol.3, No.1, pp. 3-20, 2000.
15. [15] J. Hurink, B. Jurisch, and M. Thole, “Tabu search for the job shop scheduling problem with multi-purpose machines,” Operations Research Spektrum, Vol.15, No.4, pp. 205-215, 1994.
16. [16] I.-C. Choi and D.-S. Choi, “A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups,” Computers & Industrial Engineering, Vol.42, No.1, pp. 43-58, 2002.
17. [17] M. Saidi-Mehrabad and P. Fattahi, “Flexible job shop scheduling with tabu search algorithms,” Int. J. of Advanced Manufacturing Technology, Vol.32, No.5-6, pp. 563-570, 2007.
18. [18] P. Fattahi, M. Saidi-Mehrabad, and F. Jolai, “Mathematical modeling and heuristic approaches to flexible job shop scheduling problems,” J. of Intelligent Manufacturing, Vol.18, No.3, pp. 331-342, 2007.
19. [19] K. Z. Gao, P. N. Suganthan, Q. K. Pan, T. J. Chua, T. X. Cai, and C. S. Chong, “Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives,” J. of Intelligent Manufacturing, Vol.27, No.2, pp. 363-374, 2016.
20. [20] Flexible Job Shop Problem, http://people.idsia.ch/monaldo/fjsp.html [Accessed September 31, 2017]