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.
Original language | English |
---|---|
Pages (from-to) | 6913-6931 |
Number of pages | 19 |
Journal | International Journal of Production Research |
Volume | 46 |
Issue number | 24 |
DOIs | |
Publication status | Published - 2008 Dec |
Externally published | Yes |
Keywords
- Job shop-scheduling
- Memetic algorithm
- Priority rules
ASJC Scopus subject areas
- Strategy and Management
- Management Science and Operations Research
- Industrial and Manufacturing Engineering