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, A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling, International Journal of Production Economics, vol. 141, no. 1, pp. 87 - 98, 2013.

Full text: Official version; Request a copy

Abstract

This paper addresses the multiobjective flexible job shop scheduling problem (MOFJSP) regarding minimizing the makespan, total workload, and maximum workload. The problem is solved in a Pareto manner, whose goal is to seek for the set of Pareto optimal solutions. We propose a multiobjective evolutionary algorithm, which utilizes effective genetic operators and maintains population diversity carefully. A main feature of the proposed algorithm is its simplicity – it needs only two parameters. Performance of our algorithm is compared with seven state-of-the-art algorithms on fifteen popular benchmark instances. Only our algorithm can find 70% or more non-dominated solutions for every instance.

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.

 Download

Benchmark algorithms

• Ho, N.B., Tay, J.C., Solving multiple-objective flexible job shop problems using evolution and local search, IEEE Transactions on Systems, Man, and Cybernetics – Part C, vol. 38, no. 5, pp. 674–685, 2008.

• Xing, L.N., Chen, Y.W., Yang, K.W., An efficient search method 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.

• Bagheri, A., Zandieh, M., Mahdavi, I., Yazdani, M., An artificial immune algorithm for the flexible job-shop scheduling problem, Future Generation Computer Systems, vol. 26, pp. 533–541, 2010.

• Wang, X., Gao, L., Zhang, C., Shao, X., A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. International Journal of Advanced Manufacturing Technology, vol. 51, pp. 757–767, 2010.

• Li, J.Q., Pan, Q.K., Gao, K.Z., Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems, International Journal of Advanced Manufacturing Technology, vol. 55, pp. 1159–1169, 2011.

• Li, J.Q, Pan, Q.K., Chen, J., A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems. International Journal of Production Research, vol. 50, no. 4, pp. 1063–1078, 2012.

List of non-dominated solutions

Download