A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

기술 요약: 유연한 작업 숍 스케줄링을 위한 임계 경로 기반 이중 이웃 탐색을 적용한 유전 알고리즘

문제 정의
본 논문은 현대 제조 공정에서 흔히 발생하는 강력한 NP-난해(NP-hard) 최적화 과제인 유연한 작업 숍 스케줄링 문제(Flexible Job Shop Scheduling Problem, FJSP)를 다룬다. 고정된 기계 할당을 갖는 고전적인 작업 숍 스케줄링 문제(JSP)와 달리, FJSP는 각 작업이 대안 후보군 중 하나의 기계에서 처리될 수 있도록 허용하며, 이때 처리 시간이 달라질 수 있다. 주요 목적은 모든 작업의 최대 완료 시간인 메이크스팬($C_{max}$)을 최소화하는 것이다. 이 문제는 선행 제약 조건과 기계 가용성을 충족하면서 각 작업에 대한 기계 선택과 각 기계에서의 처리 순서를 결정하는 것을 포함한다.

방법론: HGVNSA
저자들은 전역 탐색을 위한 유전 알고리즘(GA)과 국소 탐색을 위한 임계 경로 기반 변수 이웃 탐색(VNS)을 통합한 하이브리드 유전 변수 이웃 탐색 알고리즘(HGVNSA)을 제안한다.

1. 인코딩 및 디코딩: 솔루션은 작업 순서(OS) 벡터와 기계 선택(MS) 벡터라는 두 개의 층으로 구성된 인코딩을 사용하여 표현된다. 실행 가능한 스케줄을 생성하기 위해 능동적 디코딩 전략이 사용된다.
2. 집단 초기화: 품질과 다양성의 균형을 맞추기 위해 초기 집단은 다음과 같은 하이브리드 전략을 사용하여 생성된다: 전역 선택(60%, 전역 부하 증가 최소화), 지역 선택(30%, 작업 내 부하 균형), 그리고 무작위 선택(10%).
3. 유전 연산:
   • 교차(Crossover): 경로 재연결(Path-Relinking, PR) 기반 교차 연산자가 도입되었다. 단순히 무작위로 유전자를 교환하는 대신, 한 부모 솔루션을 다른 솔루션으로 체계적으로 변형하며, 부모 사이의 해 공간을 활용하기 위해 중간 솔루션들을 기록하고 평가한다.
   • 변이(Mutation): 적응형 변이 메커니즘은 개체의 적합도와 세대 수에 따라 확률을 조정한다. 두 가지 유형의 변이가 사용된다: OS 변이(작업 순서 섞기)와 MS 변이(기계 할당 변경).
   • 다양성 보존: 집단의 다양성을 유지하고 조기 수렴을 방지하기 위해 해밍 거리(Hamming distance) 기반 전략이 채택된다.
4. 임계 경로 기반 이중 이웃 VNS: GA 프레임워크 내에 내장된 이 국소 탐색은 (이산 그래프에서의 가장 긴 경로인) 임계 경로에 위치한 작업들에 집중한다. 이는 두 가지 상호 보완적인 이웃 구조를 활용한다:
   • N8 이웃: 동일한 기계 상의 작업 순서를 최적화한다. 이는 임계 블록 외부의 임계 작업을 블록의 끝점이나 블록 전/후 위치로 이동시키는 것을 허용함으로써 기존의 N5-N7 이동을 확장한 것이다.
   • k-삽입 이웃: 임계 작업을 다른 기계로 재배치한다. 이는 대안 기계들을 탐색하고 작업을 가능한 위치에 삽입하며, 순환 의존성을 확인하는 과정을 포함한다.
   • 탐색 전략: VNS 과정은 N8 이웃(낮은 계산 비용)을 우선시하며, 개선이 발견되지 않을 경우에만 k-삽입(높은 비용, 더 넓은 탐색)으로 전환하여 효율성과 탐색 깊이 사이의 균형을 보장한다.

주요 기여
본 논문은 다섯 가지 주요 기여를 기술한다:

1. 하이브리드 프레임워크: "전역 탐색 우선, 국소 탐색 후속"이라는 시너지 효과를 내는 프레임워크를 구축하여 솔루션 정확도와 계산 효율성을 효과적으로 균형 있게 조절한다.
2. 이중 이웃 통합: FJSP를 위한 단일 VNS 프레임워크 내에 N8과 k-삽입 이웃을 통합한 최초의 사례이다. 이 결합은 기계 내 순서 최적화와 기계 간 재배치를 모두 해결하여 국소 탐색 능력을 크게 향상시킨다.
3. 강화된 유전 연산자: 경로 재연결 교차와 적응형 변이 확률의 도입은 솔루션 공간을 탐색하고 수렴 안정성을 유지하는 알고리즘의 능력을 강화한다.
4. 벤치마크 성능: Brandimarte MK 벤치마크 세트에서 HGVNSA는 10개 사례 중 6개(MK01-MK04, MK08-MK09)에서 알려진 최적해에 도달하였으며, 비교 알고리즘들(HGWO, HLO-PSO, HA, SLGA, ISLGA) 중 가장 낮은 평균 상대 백분율 편차(RPD)인 0.06%를 달est하였다.
5. 실제 응용: 본 알고리즘은 A사의 기어 샤프트 가공 시나리오에 적용되었다. 전통적인 유전 알고리즘과 비교했을 때, HGVNSA는 생산 효율을 8.81% 향상시켜 공학적 실용성을 입증하였다.

결과 및 검증

• 벤치마크 테스트: MK01-MK10 사례에 대한 광범위한 실험 결과, HGVNSA는 솔루션 품질과 안정성 측면에서 비교 알고리즘들을 능가하였다. 소거 연구(Ablation studies)를 통해 VNS 구성 요소, 이중 이웃 구조 또는 적응형 메커니즘을 제거할 경우 성능이 크게 저하됨을 확인하였다(예: VNS를 제거하면 MK02의 평균 메이크스팬이 26에서 30.4로 증가함).
• 사례 연구: 15대의 기계와 59개의 작업을 포함하는 10개의 작업을 다룬 A사의 사례 연구에서, 알고리즘은 메이크스팬을 기존 GA의 522에서 476으로 단축시켰다.
• 수렴: 수렴 분석 결과, 다른 알고리즘들이 초기 급격한 수렴 이후 정체되는 반면, HGVNSA는 국소 탐색 메커니즘을 통해 솔루션을 지속적으로 정교화하며 후기 반복 단계에서 지역 최적해를 돌파함을 보여주었다.

의의
본 논문은 HGVNSA가 FJSP에 대한 효율적이고 견고한 솔루션 프레임워크를 제공하며, 전역 탐색과 국소 탐색의 균형 및 효과적인 이웃 구조 설계의 과제를 효과적으로 해결한다고 주장한다. 본 연구는 임계 경로 기반 국소 탐색과 유전적 진화를 결합하는 것이 이론적 벤치마크와 실제 산업 환경 모두에서 우수한 결과를 낳는다는 것을 입증한다. 저자들은 본 연구가 분산 스케줄링 및 지능형 이웃 선택을 위한 심층 강화 학습 연구의 토대를 마련했다고 제안하지만, 이러한 확장이 현재 연구에 구현되었다고 주장하지는 않는다.