An effective genetic algorithm for the flexible job-shop scheduling problem

[koptimizer]

📋 논문의 정보를 알려주세요.

• An effective genetic algorithm for the flexible job-shop scheduling problem
• Guohui Zhang, Liang Gao, Yang Shi
• 2011-04

📃 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.

🔎 어떤 논문인지 소개해주세요.

• Genetic algorithm을 Flexible job-shop scheduling에서 적용하기 위해 효과적인 알고리즘과 향상된 해 표현에 대해 제안합니다.
• 각 과정이 상세히 기술되어있어서 Implementation의 관점으로 읽기에 좋은 것 같습니다.

🔑 핵심 키워드를 적어주세요.

Genetic algorithm, Flexible job-shop scheduling problem(FJSP), Chromosome representation, Initialization

📎 URL

https://www.sciencedirect.com/science/article/pii/S095741741000953X?via%3Dihub

[koptimizer]

💡 방법은 무엇입니까?

• 제안은 세가지로 나눌 수 있는데, 첫 번째는 해의 표현 그리고 두 번째는 초기화 방법, 마지막으로 세 번째는 유전적 연산자입니다.
• 해의 표현(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을 유지하기 위해 다음의 방법을 사용했습니다.
  • Machine selection의 Crossover에서는 Two-point crossover, Uniform crossover를 사용했고, Operation sequence에선 Preserving order-based crossover(Lee, Yamakawa, & Lee, Yamakawa, and Lee, 1998)를 사용했습니다.
  • Mutation에서는 좀 의아한게 변이가 아니라 진화하듯이 더 좋은 선택을 임의적으로 해주도록 했습니다.

📈 실험과 그 결과는 어떻습니까?

• 실험
  1. GS+LS+RS(Random search)를 6:3:1 비율로 초기화를 진행한 것과 기존의 RS초기화랑 어떤 결과를 갖는지 비교하였습니다.
  2. 다양한 Scheduling data set에 대해서 M&G와 GENACE같은 기존에 제안된 방법과 비교하였습니다.
• 결과
  1. 초기해의 품질이 훨씬 뛰어나다보니 Makespan이 좋은 결과를 당연히 얻을 수 있었습니다.
  2. 기존에 찾아낸 최고해보다 더 좋은 새 해를 33개 발견했습니다. 문제에 따라서 근소한 차이가 있기도했지만, 대부분 해당 제안이 더 좋은 결과를 기록했습니다.

📂 차후 연구방향 및 보완점은 무엇입니까?

• 우수한 지역탐색 알고리즘과 결합하여 Global search와 Local search를 더 좋게 확장 할 수 있다고 말합니다.
• Mutation 부분이 조금 의아한게, 탐색 범위를 더 넓히는게 아니라 수렴속도를 올리도록 디자인 되어있고, 변이확률도 굉장히 낮게 설정했습니다.(0.01) 더 좋은 Mutation을 적용할 수 있지 않나 하는 생각이 들었습니다.

👍 Novelty와 논문을 통해 배운 것은 무엇입니까?

• Scheduling에서의 GA를 어떤식으로 표현해야할지 배울 수 있었습니다.
• 논문에 그림과 설명이 굉장히 자세히 나와있어서 구현하기에 매우 좋을 것 같습니다.

➿ 궁금한 점이나 추가로 읽으면 좋은 레퍼런스가 있습니까?

추가적으로 궁금한 사항에 대해서 적어주세요.
같이 읽으면 좋은 레퍼런스의 제목과 URL을 덧붙혀주세요.