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, Hsueh-Chien Cheng, and Li-Chen Fu, NNMA: An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems, Expert Systems with Applications, vol. 38, no. 5, pp. 5986 - 5999, 2011.

Full text: ScienceDirect; Unedited version

Abstract

The permutation flow shop scheduling problem is addressed in this paper. Two objectives, minimization of makespan and total flow time, are considered. We propose a memetic algorithm, called NNMA, by integrating a general multiobjective evolutionary algorithm (NSGA-II) with a problem-specific heuristic (NEH). We take NEH as a local improving procedure in NNMA and propose several adaptations including the acceptance criterion and job-insertion ordering to deal with multiple objectives and to improve its performance. We test the performance of NNMA using 90 public problem instances with different problem scales, and compare its performance with 23 algorithms. The experimental results show that our NNMA provides close performance for 30 small-scale instances and better performance for 50 medium- and large-scale instances. Furthermore, more than 70% of the net set of non-dominated solutions is updated by NNMA for these 50 instances.

Benchmark problem instances

Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, vol. 64, pp. 278–285, 1993.

Benchmark algorithms

Minella, G., Ruiz, R., Ciavotta, M., A review and evaluation of multi-objective algorithms for the flowshop scheduling problem, INFORMS Journal of Computing, vol. 20, pp. 451–471, 2008.

List of non-dominated solutions

Download