A rule-centric memetic algorithm to minimize the number of tardy jobs in the job shop

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.

Keywords:

• Job shop-scheduling
• Memetic algorithm
• Priority rules

Acknowledgements

This research is sponsored by the National Science Council under Research Grant No. NSC 95-2218-E-002-039.