A Benchmarking Suite for Flexible Job Shop Scheduling Problems with Worker Flexibility under Uncertainty

기술 요약: 불확실성 하의 작업자 유연성을 갖는 유연 작업장 스케줄링 문제를 위한 벤치마킹 스위트

문제 정의
본 논문은 **유연 작업장 스케줄링 문제 (FJSSP)**와 그 확장인 **작업자 유연성을 갖는 유연 작업장 스케줄링 문제 (FJSSP-W)**를 다룹니다. 고전적인 FJSSP 는 비용 함수 (일반적으로 완료 시간) 를 최소화하기 위해 작업을 적합한 기계에 할당하는 것을 포함하는 반면, FJSSP-W 는 인력 할당까지 통합합니다. 이러한 확장된 문제에서 작업은 특정 기계뿐만 아니라 적합한 작업자에게도 할당되어야 하며, 특정 기계 - 작업자 조합이 가공 시간을 결정합니다.

문헌에서 확인된 중요한 격차는 특히 불확실성 (예: 확률적 가공 시간, 기계 고장, 작업자 부재) 을 통합할 때 이러한 문제를 위한 표준화되고 체계적인 벤치마킹 환경이 부족하다는 점입니다. 기존 연구는 종종 솔버 간의 교차 영역 비교 (수학적 프로그래밍, 제약 프로그래밍, 시뮬레이션 기반 최적화) 를 방해하는 파편화된 임시 인스턴스 세트나 특정 실제 사례에 의존합니다.

방법론 및 벤치마크 구축
저자들은 Python 으로 구현된 포괄적인 오픈소스 벤치마킹 스위트를 제안합니다. 방법론은 세 가지 주요 구성 요소를 포함합니다:

1. 인스턴스 수집 및 확장:

   • 이 스위트는 Brandimarte, Hurink, Kacem 등 10 개의 확립된 출처에서 추출한 402 개의 고유한 FJSSP 인스턴스로 구성된 큐레이션 컬렉션을 기반으로 구축되었습니다.
   • 이러한 인스턴스는 FJSSP-W 인스턴스를 생성하기 위해 체계적으로 확장됩니다. 확장 과정은 각 작업 - 기계 조합에 작업자 집합 ($W$) 을 할당합니다.
   • 작업자 할당 로직: 각 작업 - 기계 쌍에 대해 적합한 작업자의 무작위 수를 샘플링합니다. 이러한 새로운 조합에 대한 가공 시간은 원래 기계 가공 시간을 중심으로 한 분포에서 샘플링하여 생성됩니다 (기본 범위: 기본 시간의 90% 에서 110%).
   • 특성화: 스위트는 작업 수 ($n$), 기계 수 ($m$), 작업자 수 ($w$), 작업 수 ($N$), 유연성 ($\beta$), 그리고 지속 시간 다양성 ($d_v$) 을 포함한 구체적인 인스턴스 특성을 문서화하여 기능 기반 필터링을 가능하게 합니다.

2. 이산 사건 시뮬레이션 (DES) 을 통한 불확실성 모델링:

   • 이 환경은 가공 시간 변동성, 기계 고장, 작업자 부재라는 세 가지 유형의 불확실성 시뮬레이션을 지원합니다.
   • 가공 시간: 일관되지 않은 작업 속도를 시뮬레이션하기 위해 베타 분포를 사용하여 모델링됩니다.
   • 기계 고장: 발생은 지수 분포 (스케줄당 평균 1 회 고장) 로, 지속 시간은 와이블 분포 (노이즈 없는 완료 시간의 최소 10%) 로 모델링됩니다.
   • 작업자 부재: 발생 빈도가 낮은 지수 분포와 지속 시간이 긴 와이블 분포 (노이즈 없는 완료 시간의 최소 50%) 로 모델링됩니다.
   • 솔루션은 이러한 확률적 사건의 탐색 및 시뮬레이션을 용이하게 하기 위해 방향 비순환 그래프 (DAG) 로 표현됩니다.

3. 평가 프레임워크:

   • 스위트는 인스턴스 로드, 인코딩 변환 (예: FJSSP 와 FJSSP-W 간), 그리고 성능 평가를 위한 API 를 제공합니다.
   • 지표: 주요 목표는 완료 시간을 최소화하는 것입니다. 불확실성 시뮬레이션의 경우, 강건한 완료 시간 ($C_r$) 은 여러 시뮬레이션 실행에 걸친 평균 실제 완료 시간으로 계산됩니다.
   • 통계적 분석: 프레임워크에는 솔버 성능을 엄격하게 비교하기 위한 통계적 순위 (Friedman 및 Nemenyi 검정) 및 시각화 (예: Nemenyi 다이어그램) 도구가 포함되어 있습니다.

주요 기여

• 표준화된 벤치마크 컬렉션: 연구 간 재현성과 비교 가능성을 보장하는 402 개의 FJSSP-W 인스턴스로 구성된 고정 포트폴리오의 생성.
• 오픈소스 스위트: 필요한 모델 표현 및 평가 함수를 제공함으로써 여러 최적화 패러다임 (MILP, CP, 진화 알고리즘) 을 지원하는 Python 기반 환경.
• 불확실성 통합: 문제 인스턴스에 확률성을 주입하는 체계적인 방법으로, 강건한 최적화 전략의 개발 및 평가를 가능하게 함.
• 기준선 결과: 표준화된 시간 제한 (20 분) 및 하드웨어 구성 하에서 최첨단 솔버 (Gurobi, IBM CPLEX/OR-Tools, 유전 알고리즘) 에서 도출된 "최고로 알려진" 결과 제공.

실험 결과
저자들은 402 개의 FJSSP-W 인스턴스에 대해 네 가지 솔버를 비교하여 스위트의 기능을 시연했습니다:

• 제약 프로그래밍 (CP): 다른 접근 방식을 크게 능가하여 80% 이상의 인스턴스에서 0.25 미만의 상대 편차 ($\delta_{rel}$) 를 달성했습니다.
• 유전 알고리즘 (GA): 잘 수행되었으며 MILP 및 탐욕적 접근 방식을 크게 능가했으나 CP 에 뒤처졌습니다.
• 혼합 정수 선형 프로그래밍 (MILP): 문제 규모에 어려움을 겪었으며, 메모리 제약과 변수 수로 인해 많은 인스턴스가 시간 제한 내에 해결되지 못했습니다.
• 탐욕 알고리즘: 기준선으로 작용하며 가장 낮은 성능을 보였습니다.

강건성 시뮬레이션 (Fattahi20 인스턴스 사용) 에서 프레임워크는 불확실성 하에서 스케줄의 저하를 성공적으로 시각화하고, 스케줄 안정성을 평가하기 위해 강건한 완료 시간 및 강건성 비율 ($R$) 을 계산했습니다.

중요성 및 주장
본 논문은 이 작업이 생산 스케줄링 연구에서 표적 알고리즘 개발 및 일관된 성능 평가를 위한 기반을 마련한다고 주장합니다. 현재 벤치마킹 관행의 파편화를 해결함으로써, 이 스위트는 다음을 가능하게 합니다:

• 공정한 비교: 다양한 솔버 및 문제 하위 도메인에 걸친 엄격하고 재현 가능한 평가.
• 알고리즘 개발: 인스턴스 필터링을 통해 특정 문제 그룹에 대한 연산자 개발 지원.
• 강건성 평가: 결정론적 최적화를 넘어 솔버가 실제 세계의 불확실성을 어떻게 처리하는지 평가할 수 있는 능력.

저자들은 이 스위트가 주로 시뮬레이션 기반 최적화 (SBO) 와 진화 알고리즘을 위해 설계되었지만, MILP 와 CP 를 위한 모델 표현을 제공함으로써 패러다임 간 비교를 가능하게 한다고 강조합니다. 그들은 과학적 재현성을 보장하기 위해 고정 인스턴스 세트를 사용할 것을 권장하며, 향후 연구를 촉진하기 위해 실험 매개변수와 하드웨어 사양 보고의 투명성을 촉구합니다.