Priority Rule-Based Construction Procedure Combined with Genetic Algorithm for Flexible Job-Shop Scheduling Problem
Soichiro Yokoyama, Hiroyuki Iizuka, and Masahito Yamamoto
Graduate School of Information Science and Technology, Hokkaido University
Kita 14, Nishi 9, Kita-ku, Sapporo, Hokkaido 060-0814, Japan
The heuristic method we propose solves the flexible job-shop scheduling problem (FJSP) using a solution construction procedure with priority rules. FJSP is more complex than classical scheduling problems in that operations are processed on one of multiple candidate machines, one of which must be selected to get a feasible solution. The solution construction procedure with priority rules is implemented on top of the efficient existing method for solving the FJSP which consists of a genetic algorithm and a local search method. The performance of the proposed method is analyzed using various benchmark problems and it is confirmed that our proposed method outperforms the existing method on problems with particular conditions. The conditions are further investigated by applying the proposed method on newly created benchmark.
-  S. S. Panwalkar and W. Iskander, “A Survey of Scheduling Rules,” Operations Research, Vol.25, No.1, pp. 45-61, 1977.
-  Y. Tamura, M. Yamamoto, I. Suzuki, and M. Furukawa, “Acquisition of Dispatching Rules for Job-Shop Scheduling Problem by Artificial Neural Networks Using PSO,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.17, No.5, pp. 731-738, 2013.
-  E. Nowicki and C. Smutnicki, “A Fast Taboo Search Algorithm for the Job Shop Problem,” Management Science, Vol.42, No.6, pp. 797-813, 1996.
-  C. Bierwirth, “A generalized permutation approach to job shop scheduling with genetic algorithms,” Operations-Research-Spektrum, Vol.17, No.2-3, pp. 87-92, 1995.
-  R. Q. d.-e. ji and Y. Wang, “A new hybrid genetic algorithm for job shop scheduling problem,” Computers & Operations Research, Vol.39, No.10, pp. 2291-2299, 2012.
-  M. Mastrolilli and L. M. Gambardella, “Effective neighbourhood functions for the flexible job shop problem,” J. of Scheduling, Vol.3, No.1, pp. 3-20, 2000.
-  F. Pezzella, G. Morganti, and G. Ciaschetti, “A genetic algorithm for the Flexible Job-shop Scheduling Problem,” Computers & Operations Research, Part Special Issue: Search-based Software Engineering, Vol.35, No.10, pp. 3202-3212, 2008.
-  G. Zhang, L. Gao, and Y. Shi, “An effective genetic algorithm for the flexible job-shop scheduling problem,” Expert Systems with Applications, Vol.38, No.4, pp. 3563-3573, 2011.
-  J. Gao, L. Sun, and M. Gen, “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems,” Computers & Operations Research, Part Special Issue: Bio-inspired Methods in Combinatorial Optimization, Vol.35, No.9, pp. 2892-2907, 2008.
-  Y. Yuan and H. Xu, “Flexible job shop scheduling using hybrid differential evolution algorithms,” Computers & Industrial Engineering, Vol.65, No.2, pp. 246-260, 2013.
-  N. B. Ho, J. C. Tay, and E. M.-K. Lai, “An effective architecture for learning and evolving flexible job-shop schedules,” European J. of Operational Research, Vol.179, No.2, pp. 316-333, 2007.
-  J. C. Tay and N. B. Ho, “Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems,” Computers & Industrial Engineering, Vol.54, No.3, pp. 453-473, 2008.
-  K.-M. Lee, T. Yamakawa, and K.-M. Lee, “A genetic algorithm for general machine scheduling problems,” Proc. of the 2nd Int. Conf. on Knowledge-Based Intelligent Electronic Systems (KES’98), Vol.2, pp. 60-66, Apr. 1998.
-  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.
-  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.
-  S. Dauzre-Prs 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.