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.
- Job shop-scheduling
- Memetic algorithm
- Priority rules
ASJC Scopus subject areas
- Strategy and Management
- Management Science and Operations Research
- Industrial and Manufacturing Engineering