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 Li-Chen Fu, A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop, International Journal of Production Research, vol. 46, no. 24, pp. 6913 - 6931, 2008.

Full text: Informaworld ; Unedited version

Abstract

This paper addresses the job shop-scheduling problem with minimizing the number of tardy jobs as the objective. This problem is usually treated as a
job-sequencing problem, and the permutation-based representation of solutions was commonly used in the existing search-based approaches. In this paper, the flaw of the permutation-based representation is discussed, and a rule-centric concept is proposed to deal with it. A memetic algorithm is then developed to realize the proposed idea by tailored genome encoding/decoding schemes and a local search procedure. Two benchmark approaches, a multi-start hill-climbing approach and a simulated annealing approach, are compared in the experiments. The results show that the proposed approach significantly outperforms the benchmarks.

Problem instances

download