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, Multiobjective permutation flow shop scheduling using a memetic algorithm with an NEH-based local search, Lecture Notes in Computer Science (Proc. of International Conference on Intelligent Computing, ICIC 2009), vol. 5754, pp. 813 - 825, 2009.

Full text: SpringerLink

Abstract

In this paper we address scheduling of the permutation flow shop with minimization of makespan and total flow time as the objectives. We propose a memetic algorithm (MA) to search for the set of non-dominated solutions (the Pareto optimal solutions). The proposed MA adopts the permutation-based encoding and the fitness assignment mechanism of NSGA-II. The main feature is the introduction of an NEH-based neighborhood function into the local search procedure. We also adjust the size of the neighborhood dynamically during the execution of the MA to strike a balance between exploration and exploitation. Forty public benchmark problem instances are used to compare the performance of our MA with that of twenty-seven existing algorithms. Our MA provides close performance for small-scale instances and much better performance for large-scale instances. It also updates more than 90% of the net set of non-dominated solutions for the large-scale 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

• TA11-20 (20 jobs, 10 machines)

• TA21-30 (20 jobs, 20 machines)

• TA41-50 (50 jobs, 10 machines)

• TA51-60 (50 jobs, 20 machines)

In the above files, [1] after each solution means that this solution was found by our approach, and [2] means that this solution was found by Minella et al.' approach.