A hybrid of genetic algorithm and bottleneck shifting for flexible job shop scheduling problemA hybrid of genetic algorithm and bottleneck shifting for flexible job shop scheduling problem

ABSTRACT

Flexible job shop scheduling problem (fJSP) is an extension of the classical job shop scheduling problem, which provides a closer approximation to real scheduling problems. We develop a new genetic algorithm hybridized with an innovative local search procedure (bottleneck shifting) for the fJSP problem. The genetic algorithm uses two representation methods to represent solutions of the fJSP problem. Advanced crossover and mutation operators are proposed to adapt to the special chromosome structures and the characteristics of the problem. The bottleneck shifting works over two kinds of effective neighborhood, which use interchange of operation sequences and assignment of new machines for operations on the critical path. In order to strengthen the search ability, the neighborhood structure can be adjusted dynamically in the local search procedure. The performance of the proposed method is validated by numerical experiments on several representative problems.

REFERENCES

• 1: P. Brucker , R. Schlie, Job-shop scheduling with multi-purpose machines, Computing, v.45 n.4, p.369-375, 1990 [doi>10.1007/BF02238804]
• 2: Chambers, J. B., Classical and Flexible Job Shop Scheduling by Tabu Search. PhD thesis, University of Texas at Austin, Austin, U.S.A., 1996.
• 3: Mastrolilli, M. and Gambardella, L. M., Effective neighborhood functions for the flexible job shop problem. J. Sched., 3, 3--20, 2000.
• 4: Yang, J.-B., GA-based discrete dynamic programming approach for scheduling in FMS environments. IEEE Trans. Systems, Man, and Cybernetics-Part B, 31(5), 824--835, 2001.
• 5: Kacem, I., hammadi, S. and Borne, P., Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans. Systems, Man, and Cybernetics-Part C, 32(1), 1--13, 2002.
• 6: Wu, Z. and Weng, M. X., Multiagent scheduling method with earliness and tardiness objectives in flexible job shops. IEEE Trans. System, Man, and Cybernetics-Part B, 35(2), 293--301, 2005.
• 7: Weijun Xia , Zhiming Wu, An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems, Computers and Industrial Engineering, v.48 n.2, p.409-425, March 2005 [doi>10.1016/j.cie.2005.01.018]
• 8: Zhang, H. and Gen, M., Multistage-based genetic algorithm for flexible job-shop scheduling problem. Journal of Complexity International, 11, 223--232, 2005.
• 9: Runwei Cheng , Mitsuo Gen , Yasuhiro Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithms—I: representation, Computers and Industrial Engineering, v.30 n.4, p.983-997, Sept. 1996 [doi>10.1016/0360-8352(96)00047-2 ]
• 10: Runwei Cheng , Mitsuo Gen , Yasuhiro Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies, Computers and Industrial Engineering, v.36 n.2, p.343-364, April 1999 [doi>10.1016/S0360-8352(99)00136-9 ]
• 11: Mitsuo Gen , Runwei Cheng, Genetic Algorithms, John Wiley & Sons, Inc., New York, NY, 1999
• 12: Mitsuo Gen , Runwei Cheng, Genetic Algorithms, John Wiley & Sons, Inc., New York, NY, 1999
• 13: Joseph Adams , Egon Balas , Daniel Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science, v.34 n.3, p.391-401, March 1988
• 14: Egon Balas , Alkis Vazacopoulos, Guided Local Search with Shifting Bottleneck for Job Shop Scheduling, Management Science, v.44 n.2, p.262-275, February 1998
• 15: Goncalves, J. F., Mendes, J. J. M., Resende, M. G.. C., A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research, 167, 77--95, 2005
• 16: Kacem, I., Hammadi, S. and Borne, P., Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation, 60, 245--276, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance

Keywords:
bottleneck shifting, flexible job shop scheduling problem, genetic algorithms, neighborhood structure