The Price of Optimality Under Uncertainty: A Predictive–Reactive Robustness Analysis of Exact, Metaheuristic, and Dispatching-Rule Scheduling for the Dynamic Job-Shop Problem

기술 요약: 불확실성 하에서의 최적성의 대가

문제 정의
본 연구는 불확실성 하에서의 동적 작업 숍 스케줄링 문제(JSSP)를 다룬다. JSSP는 일반적으로 결정론적 벤치마크에서 메이크스팬($C_{max}$)을 최소화하기 위해 해결되는 전형적인 NP-hard 문제이지만, 실제 작업 현장은 기계 고장, 확률적 처리 시간, 새로운 작업의 동적 도착이라는 세 가지 주요 교란에 노출되어 있다. 본 연구의 핵심 질문은 결정론적(nominal) 데이터 하에서 최적인 스케줄이 교란 상황에서 실행될 때도 여전히 선호될 수 있는지를 조사하는 것이다. 특히, 본 논문은 "최적성의 대가(price of optimality)", 즉 이론적으로 완벽한 스케줄을 달성하는 것과 현실이 계획과 달라질 때 견고성(robustness)을 유지하는 것 사이의 트레이드오프를 비교한다.

방법론
저자는 이산 사건 기반의 예측-반응형 평가 하네스를 사용하여 통제된 패러다임 수준의 비교를 수행한다. 본 연구는 16개의 Fisher–Thompson 및 Lawrence 벤치마크 인스턴스(6×6에서 20×10 범위)에 대해 9가지 교란 체제(고장, 확률적 시간, 동적 도착 각각에 대해 3가지 심각도 적용)를 대상으로 세 가지 구별된 솔루션 군을 평가한다.

1. 솔루션 패러다임:

   • 정밀 솔버 (CP-SAT): 인증된 최적(또는 준최적) 예측 스케줄을 생성하는 제약 프로그래밍 솔버이다. 이는 결정론적 데이터에 대한 "품질 상한선(quality ceiling)"을 나타낸다.
   • 메타휴리스틱 (유전 알고리즘 - GA): 고정된 계산 예산을 가진 순열 기반 유전 알고리즘으로, 인증되지는 않았으나 고품질의 예측 스케줄을 생성한다.
   • 우선순위 디스패칭 규칙 (PDRs): 사전 계산된 스케줄 없이 각 이벤트 발생 시마다 결정을 내리는 9가지 온라인 규칙(SPT, LPT, MWKR, LWKR, MOR, LOR, FIFO, EDD, CR)이다.

2. 실행 및 복구 정책:

   • 오프라인 방식(CP-SAT 및 GA)은 우측 이동(right-shift) 복구 정책을 사용한다. 확정된 작업 순서는 고정되며, 교란은 작업을 지연시킬 뿐 순서를 바꾸지는 않는다.
   • PDRs는 매 이벤트마다 우선순위를 다시 결정하는 온라인 방식으로 작동한다.
   • 동적 도착은 사전 계산된 스케줄이 예측할 수 없는 제약 조건인 '유휴 기계 간격'으로 새로운 작업을 흡수함으로써 처리된다.

3. 실험 설계:

   • 교란 모델: 기계 고장은 목표 가용성($A_k \in \{0.95, 0.80\}$)을 타겟팅하도록 보정된 갱신 과정(renewal process)을 따른다. 처리 시간은 단위 평균 로그-노멀 승수($s \in \{0.10, 0.50\}$)를 사용한다. 동적 도착는 목표 가동률($\rho \in \{0.70, 0.95\}$)을 타겟팅하도록 보정된 포아송 과정을 따른다.
   • 지표:
     • 견고성 지수 (Robustness Index, RI): 교란 하에서의 메이크스팬이 해당 방법론 자체의 결정론적(nominal) 메이크스팬 대비 얼마나 상대적으로 저하되었는지를 나타낸다.
     • 실현 상대 백분율 편차 (Realized Relative Percentage Deviation, RPD): 인증된 최적해 대비 섭동(perturbed)된 메이크스팬의 편차로, 방법론 간의 실제 솔루션 품질 비교를 가능하게 한다.
   • 통계적 프로토콜: 분석에는 30회의 반복 시나리오(총 47,520회 실행)가 포함된다. 쌍별 비교에는 exact Wilcoxon signed-rank test를 사용하며, 공동 순위 산정에는 Friedman test와 Nemenyi 사후 분석을 사용한다.

주요 결과
연구 결과, 결정론적 품질과 견고성 사이의 결정적인 역전 현상이 보고되었다:

1. 결정론적 성능 (Nominal Performance): 예상대로 정밀 솔버(CP-SAT)가 최적해 대비 평균 RPD 3.08%를 달성하며 압도하였고, 그 뒤를 GA(6.28%)가 이었다. 가장 우수한 디스패칭 규칙들(MWKR, MOR)은 유의미하게 뒤처졌다(12.07% 및 14.15%).
2. 견고성 순위 (Robustness Ranking): 교란 상황에서는 순위가 역전된다. 정밀 솔버와 GA는 가장 덜 견고한 방법들(Friedman 순위 각각 10.14 및 9.82)인 반면, 모든 디스패칭 규칙은 유의미하게 더 견고했다(순위 3.95–5.77). 정밀 솔버의 최적화된 조밀함(compactness)은 지연을 흡수할 여유(slack)를 남기지 않아, 모든 교란이 완전히 전파되도록 만든다.
3. 실현 품질 역전 (Realized Quality Crossover):
   • 기계 고장: MWKR 및 MOR 규칙이 정밀 솔버를 추월하여 실현 품질에서 우위를 점했다(CP-SAT의 46.07% 대비 MWKR 42.97%, MOR 43.20% RPD).
   • 확률적 처리 시간: 정밀 솔버가 근소한 차이로 리드를 유지하지만, 결정론적 우위가 약 9%에서 3% 미만으로 줄어든다.
   • 동적 도착: 온라인 규칙이 압도적으로 우세하다. 정밀 솔버와 GA는 최악의 방법이 된다(RPD 각각 175.30% 및 177.02%). 이는 스케줄 생성 이후에 도착하는 작업을 위한 계획을 세울 수 없기 때문이다.

주요 기여

1. 패러다임 수준의 견고성 비교: 본 연구는 공통된 통제된 예측-반응형 하네스 상에서 정밀 솔버, 메타휴리틱, 그리고 전체 디스패칭 규칙 세트를 최초로 직접 비교하였다.
2. 최적성-견고성 역전의 증거 제시: 정밀 최적 스케줄이 결정론적 데이터에서는 최고의 방법이지만 동시에 가장 덜 견고하다는 것을 정량화하였으며, 견고성 순위가 결정론적 품질 순위와 사실상 반대로 나타남을 입증하였다.
3. 교란 임계점 식별: 본 논문은 교란 수준이 높아짐에 따라 정밀 솔버의 결정론적 우위가 침식되고 역전되어, 단순한 디스패칭 규칙(특히 MWKR 및 MOR)이 더 우수한 실현 스케줄을 제공한다는 점을 밝혀냈다.
4. 방법론적 명확화: 연구는 *상대적 저하(RI)*와 *실현 품질(RPD)*의 구분을 강조한다. RI만을 신뢰하는 것이 얼마나 오해의 소지가 있는지 보여준다. 예를 들어, 결정론적 스케줄이 부실한 규칙(예: EDD)은 저하될 여지가 적기 때문에 "견고해" 보일 수 있지만, MWKR과 같은 규칙은 경쟁력 있는 결정론적 성능과 우아한 저하(graceful degradation)를 동시에 갖추고 있음을 입이 증명한다.

의의 및 주장
본 논문은 정밀한 최적성과 교란에 대한 견고성이 서로 충돌하는 목표임을 결론짓는다. "최적성의 대가"는 높다: 최적으로 조밀하게 구성된 스케줄은 불확실성을 흡수할 여유(slack)가 부족하기 때문에 구조적으로 취약하다.

저자는 교란이 빈번한 환경에서 계산 비용이 들지 않는 단순한 디스패칭 규칙(특히 MWKR 또는 MOR)이 단순히 차선책이 아니라, 자주 **더 우수한 데플로이 정책(deployed policy)**이 된다고 주장한다. 이러한 규칙들은 별도의 재계획 없이도 교란을 피해 노력을 자연스럽게 재배치하는 로드 밸런싱 메커니즘 역할을 한다. 본 연구는 교란에 따른 정책 선택을 제안한다: 정밀 솔버는 거의 결정론적인 환경에서만 가치가 있으며, 교란이 심화될수록 정밀 솔버의 효용은 급격히 약화되고 온라인 규칙이 실현 성능 측면에서 최적의 선택이 된다. 이러한 결과는 결정론적 벤치마크에서 얻은 직관에 도전하며, 동적인 환경에서는 "완벽한" 오프라인 계획보다 "충분히 좋은" 온라인 적응력이 종종 더 뛰어난 성과를 낸다는 점을 시사한다.