Adaptive Mutation Driven Harris Hawk Optimization Algorithm in Hybrid Flow Workshop Scheduling with Robotic Arm

기술 요약: 로봇 팔이 포함된 하이브리드 플로우 워크숍 스케줄링을 위한 적응형 변이 구동 해리스 호크 최적화 알고리즘

문제 정의
본 논문은 지능형 제조에서 흔히 발생하는 복잡한 조합 최적화 과제인 로딩/언로딩 기계가 포함된 하이브리드 플로우 숍 스케줄링 문제(HFSP-LUM)를 다룹니다. 이 특정 변형 모델은 $n$개의 작업물을 $m$개의 공정에 스케줄링하며, 각 공정은 병렬 동일 장비를 포함하고, 결정적으로 인접 단계 간의 자재 운반을 담당하는 로봇 팔이 포함됩니다. 이 문제는 고차원성, 강력한 제약 조건(예: 비선점형 처리, 단일 작업 로봇 팔, 공정 순서), 그리고 최대 완료 시간($C_{max}$) 최소화 필요성을 특징으로 합니다. 저자들은 기존의 수동 스케줄링과 기존 휴리스틱 알고리즘이 이러한 고차원적이고 제약이 많은 환경에서 동적인 생산 요구, 조기 수렴 및 불충분한 전역 탐색 능력 문제로 인해 어려움을 겪는다고 언급합니다.

방법론
이러한 과제를 해결하기 위해 저자들은 **적응형 변이 구동 해리스 호크 최적화 알고리즘(AMDHHO)**을 제안합니다. 본 방법론은 HFSP-LUM의 수학적 모델과 향상된 메타휴리스틱 솔버를 통합합니다.

1. 수학적 모델링:

   • $C_{max}$를 최소화하는 것을 목표로 혼합 정수 프로그래밍 모델을 구축합니다.
   • 이 모델은 공정 순서, 기계 할당(한 번에 하나의 작업물만 기계 점유), 로봇 팔의 독점성(한 번에 하나의 운반 작업만 수행), 그리고 시간적 의존성(시작 시간은 운반 및 처리 완료 시간을 준수해야 함)에 대한 제약 조건을 포함합니다.
   • 결정 변수에는 작업물 처리 순서, 기계 할당, 로봇 팔 작업 할당이 포함됩니다.

2. 알고리즘 설계 (AMDHHO):

   • 기본 프레임워크: 알고리즘은 해리스 호크의 "매복 포위" 사냥 전술을 시뮬레이션하며 탐색(무작위 순찰)과 착취(먹이 추적 및 공격)를 교대로 수행하는 표준 해리스 호크 최적화(HHO) 프레임워크를 기반으로 구축되었습니다.
   • 하이브리드 인코딩: 솔루션을 표현하기 위해 3차원 하이브리드 인코딩 구조를 사용합니다:
     • 공정 순서 벡터 (PSV): 작업물의 우선순위를 결정합니다.
     • 기계 할당 벡터 (MAV): 작업물에 특정 병렬 기계를 할당합니다.
     • 로봇 팔 할당 벡터 (RAV): 단계 간 운반을 위한 로봇 팔을 할당합니다.
   • 주요 개선 사항:
     • 레비 비행(Levy Flight) 교란: 전역 탐색을 강화하고 조기 수렴을 방지하기 위해 탐색 메커니즘에 통합되었습니다.
     • 적응형 변이 확률: 반복 횟수와 인구 에너지 상태에 따라 변이 확률을 조정하는 동적 전략을 사용하여, 초기 단계의 전역 탐색과 후기 단계의 국소 개발 사이의 균형을 맞춥니다.
     • 다중 방식 교차(Multi-method Crossover): 순서 최적화를 위한 부분 매핑 교차(PMX)와 기계/로봇 할당을 위한 균등 교차를 사용하며, 적응형 확률 제어를 적용합니다.
     • 디코딩 전략: 3D 벡터를 실행 가능한 스케줄로 변환하는 단계별 디코딩 메커니즘을 통해, 자원 및 시간 제약을 엄격히 준수하면서 시작/완료 시간을 계산합니다.

주요 기여

• 알고리즘 혁신: 적응형 변이 및 레비 비행 메커니즘을 HHO 프레임워크에 통합하여 HFSP-LUM을 구체적으로 겨냥한 AMDHHO를 개발했습니다.
• 포괄적 모델링: 로봇 팔 제약과 운반 시간을 명시적으로 고려하는 엄격한 수학적 모델을 구축하였으며, 이는 표준 플로우 숍 모델에서 종종 단순화되거나 무시되는 부분입니다.
• 하이브리드 인코딩 및 디코딩: 로봇 보조 하이브리드 플로우 숍의 다차원 결정 변수에 맞춤화된 특정 인코딩/디코딩 체계를 제안했습니다.
• 실증적 검증: Taillard 기반의 표준 벤치마크 인스턴스와 20개 작업물, 11개 기계, 3개 로봇 팔을 포함하는 실제 산업 사례 연구를 통해 광범위한 테스트를 수행했습니다.

실험 결과
저자들은 다섯 가지 규모(10개에서 50개의 작업물 범위)의 문제 인스턴스에 대해 표준 HHO, 메이플라이 알고리즘(MA), 유전 알고리즘(GA), 비틀 최적화 알고리즘(DO)과 비교 실험을 진행했습니다.

• 표준 벤치마크:

  • 가장 큰 규모의 테스트(작업물 50개, 5단계, 5개 기계)에서 AMDHHO는 492.6분의 $C_{max}$를 달성했습니다.
  • 이는 유전 알고리즘(557.8분) 대비 약 11.7%, 표준 HHO 대비 5.0% 개선된 수치입니다.
  • AMDHHO는 표준 편차 3.27을 기록하며 우수한 안정성을 보였으며, 이는 GA의 7.92보다 현저히 낮은 수치입니다.
  • 수렴 속도 또한 눈에 띄게 빨랐습니다. 동일한 문제 규모에서 AMDHHO는 57회 반복 만에 수렴한 반면, GA는 127회가 필요했습니다.

• 절제 연구 (Ablation Studies):

  • 실험을 통해 적응형 변이와 레비 비행의 결 조합이 성능의 주요 동력임을 확인했으며, 이는 표준 HHO와 비교했을 때 최적해는 약 13%, 평균해는 약 15% 개선되었습니다.
  • 적응형 변이 메커니즘은 솔루션의 변동성을 크게 줄였습니다 (표준 편차 감소율 42.6–45.2%).

• 실제 적용 (쑤저우 정밀 부품 제조):

  • 20개 작업물과 3개의 로봇 팔이 있는 생산 라인에 적용되었습니다.
  • AMDHHO는 최대 완료 시간을 기존 수동 계획인 768분에서 683분으로 단축하여, **85분(11.1%)**을 절감했습니다.
  • 평균 대기 시간은 39.8% 감소하였고, 자원 활용도는 **82.7%**로 증가했습니다.
  • 장비 고장을 시뮬레이션한 동적 시나리오에서 알고리즘은 약 9.6초 만에 조정된 스케줄을 생성하여 실시간 적응성을 입증했습니다.

의의 및 주장
본 논문은 AMDHHO 알고리즘이 지능형 제조 환경의 복잡한 워크숍 스케줄링을 위한 효율적이고 견고한 솔루션을 제공한다고 주장합니다. 저자들은 이 알고리즘이 전역 탐색과 국소 개발 사이의 균형을 성공적으로 맞추어, 고차원적이고 제약이 강한 환경에서 기존 군집 지능 알고리즘의 한계를 극복했다고 단언합니다. 결과는 AMDHHO가 생산 주기를 단축하고 자원 활용도를 높이는 데 있어 상당한 실질적 가치를 제공함을 시사합니다. 본 연구는 AMDHHO의 동적 적응 메커니즘이 장비 고기와 같은 동적 이벤트에 대한 빠른 대응이 필요한 환경에 특히 적합하다는 점을 강조합니다.