Associate Professor Tsung-Che Chiang

Department of Computer Science and Information Engineering
National Taiwan Normal University

Tel: +886-2-77346692    Fax: +886-2-29322378    Email

Tsung-Che Chiang and Hsiao-Jou Lin, Flexible Job Shop Scheduling using a Multiobjective Memetic Algorithm, Lecture Notes in Artificial Intelligence (Proc. of International Conference on Intelligent Computing), vol. 6839, pp. 49 - 56, August, 2011.

Full text: Official version; Full-length manuscript

Abstract

This paper addresses the flexible job shop scheduling problem with minimization of the makespan, maximum machine workload, and total machine workload as the objectives. A multiobjective memetic algorithm is proposed. It belongs to the integrated approach, which deals with the routing and sequencing sub-problems together. Dominance-based and aggregation-based fitness assignment methods are used in the parts of genetic algorithm and local search, respectively. The local search procedure follows the framework of variable neighborhood descent algorithm. The proposed algorithm is compared with three benchmark algorithms using fifteen classic problem instances. Its performance is better in terms of the number and quality of the obtained solutions.

Benchmark problem instances

• Brandimarte, P., Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research, vol. 41, pp. 157 - 183, 1993.

• Kacem, I., Hammadi, S., Borne, P., Pareto-optimality approach for flexible job shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic,  Mathematics and Computers in Simulation, vol. 60, pp. 245–276, 2002.

Benchmark algorithms

• Xing, L.N., Chen, Y.W., Yang, K.W., An efficient search model for multi-objective flexible job shop scheduling problems, Journal of Intelligent Manufacturing, vol. 20, pp. 283 - 293, 2009.

• Li, J.Q., Pan, Q.K., Liang, Y.C., An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems, Computers & Industrial Engineering, vol. 59, pp. 647 - 662, 2010.

• Moelehi, G., Mahnam, M., A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search, International Journal of Production Economics, vol. 129, pp. 14 - 22, 2011.

List of non-dominated solutions

Download