An effective genetic algorithm for the flexible job-shop scheduling problem
Guohui Zhang, Liang Gao, Yang Shi
2011-04
:page_with_curl: Abstract(본문)
In this paper, we proposed an effective genetic algorithm for solving the flexible job-shop scheduling problem (FJSP) to minimize makespan time. In the proposed algorithm, Global Selection (GS) and Local Selection (LS) are designed to generate high-quality initial population in the initialization stage. An improved chromosome representation is used to conveniently represent a solution of the FJSP, and different strategies for crossover and mutation operator are adopted. Various benchmark data taken from literature are tested. Computational results prove the proposed genetic algorithm effective and efficient for solving flexible job-shop scheduling problem.
:mag_right: 어떤 논문인지 소개해주세요.
Genetic algorithm을 Flexible job-shop scheduling에서 적용하기 위해 효과적인 알고리즘과 향상된 해 표현에 대해 제안합니다.
각 과정이 상세히 기술되어있어서 Implementation의 관점으로 읽기에 좋은 것 같습니다.
제안은 세가지로 나눌 수 있는데, 첫 번째는 해의 표현 그리고 두 번째는 초기화 방법, 마지막으로 세 번째는 유전적 연산자입니다.
해의 표현(MSOS)
하나의 해(Chromosome)는 Machine selection과 Operation sequence로 이루이지고, 각 Part는 Operation의 갯수만큼 길이를 부여받습니다.
Machine selection은 배열의 형태이며, 각 Job의 Operation이 어떤 machine을 선택할지 정수의 형태로 순서대로 들어갑니다.
Operation sequence 또한 배열의 형태이며, 배열의 왼쪽부터 우선 순서인 Job이 정수의 형태로 들어갑니다. 이 때, 중복된 정수는 해당 Job의 다음 Operation이 할당되었음을 의미합니다.
해당 방법으로 해를 표현하면 Crossover와 Mutation단에서 항상 Feasible solution이기 때문에 Repairing나 Feasible check가 필요하지 않습니다.
초기화 방법
Genetic algorithm에서 초기해의 품질은 전체 성능을 크게 좌우합니다. 스케줄링에서의 초기화는 Feasible까지 고려되어야 하기 때문에 어렵습니다. 해당 제안에서는 Global selection과 Local selection이라는 방법을 고안해서 품질과 Feasible을 동시에 잡았습니다.
Global selection과 Local selection의 차이는 Job마다 독립적인 시간으로 고려할지입니다.
유전적 연산자
Genetic algorithm에서 반복적으로 시행되는 Crossover와 Mutation에서 MSOS로 만들어진 해의 Feasible을 유지하기 위해 다음의 방법을 사용했습니다.
:clipboard: 논문의 정보를 알려주세요.
:page_with_curl: Abstract(본문)
:mag_right: 어떤 논문인지 소개해주세요.
:key: 핵심 키워드를 적어주세요.
Genetic algorithm, Flexible job-shop scheduling problem(FJSP), Chromosome representation, Initialization
:paperclip: URL
https://www.sciencedirect.com/science/article/pii/S095741741000953X?via%3Dihub