Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling

기술 요약: 저비용 라벨, 신뢰할 수 있는 선택

문제 제기
본 논문은 선택 하이퍼휴리스틱의 관점에서 Job Shop Scheduling Problem(JSSP)을 다룹니다. 학습 기반 하이퍼휴리스틱은 고정된 디스패칭 규칙과 엔드투엔드 학습 생성기 사이의 중간 지점을 제공하며, 실현 가능성과 해석 가능성을 유지하지만 두 가지 주요 병목 현상에 직면합니다:

1. 라벨 생성 비용: 지도 학습은 부분 스케줄에서 최종 상태까지 후보 디스패칭 규칙을 "롤아웃"하여 생성된 라벨을 필요로 합니다. 모든 의사 결정 지점에서 모든 후보 규칙에 대한 완전한 롤아웃은 $O(|H|T)$의 계산 비용을 초래하며, 여기서 $|H|$는 규칙의 수이고 $T$는 남은 의사 결정 횟수입니다.
2. 선택의 신뢰성: 학습된 선택기는 노이즈나 과적합으로 인해 강력한 기본 규칙보다 약간 개선된 결과를 우연히 예측할 수 있습니다. 예측된 점수가 가장 낮은 규칙을 맹목적으로 따르는 것은 견고한 고정 규칙에 비해 성능 저하로 이어질 수 있습니다.

저자들은 이러한 감독 라벨을 생성하는 비용과 결과적인 선택기의 신뢰성 사이의 트레이드오프를 연구하고자 하며, 특히 예측된 이득이 신뢰할 수 있을 때만 학습된 모델이 강력한 기본 규칙에서 벗어나지 않도록 하는 방법에 초점을 맞춥니다.

방법론
제안된 접근법인 롤아웃 보정 하이퍼휴리스틱은 세 가지 핵심 구성 요소를 통합합니다:

1. 후회 정규화 롤아웃 라벨:
   원시 makespan 또는 하한 정규화 makespan 을 타겟으로 사용하는 대신, 저자들은 상태별 후회 라벨을 정의합니다:
   $$r(s, h) = \frac{m(s, h) - \min_{h' \in H_s} m(s, h')}{\min_{h' \in H_s} m(s, h')}$$
   여기서 $m(s, h)$는 상태 $s$에서 규칙 $h$를 적용하여 얻은 makespan 입니다. 이는 타겟을 특정 상태에서의 최상위 규칙이 후회 0 을 갖는 로컬 순위 신호로 변환하여, 해당 특정 컨텍스트 내 규칙들의 상대적 성능을 격리합니다.

2. 불확실성 게이트 선택:
   시스템은 각 후보 규칙에 대한 후회를 예측하기 위해 컨텍스트 K-최근접 이웃 (KNN) 회귀기를 사용합니다. 신뢰성을 보장하기 위해 게이트 메커니즘이 도입됩니다. 선택기는 예측된 최상위 규칙 ($h^*$) 으로만 고정 기본 규칙 ($h_0$, 훈련 세트에서 최상의 고정 규칙으로 선택됨) 에서 전환하며, 기대 이득이 불확실성 조정 마진을 초과할 때만 전환합니다:
   $$\pi_{gated}(s) = \begin{cases} h^* & \text{if } \hat{r}(s, h_0) - \hat{r}(s, h^*) > \lambda \hat{\sigma}(s, h^*) \\ h_0 & \text{otherwise} \end{cases}$$
   여기서 $\hat{\sigma}$는 $k$-최근접 이웃의 표준 편차 (불확실성 추정치로 작용) 이며, $\lambda$는 전환의 공격성을 조절하는 하이퍼파라미터입니다.

3. 롤아웃 예산 트레이드오프:
   저자들은 롤아웃 폭($b$, 평가된 후보 규칙의 수) 과 롤아웃 깊이($\kappa$, 기본 규칙으로 복귀하기 전에 후보 규칙이 따르는 단계 수) 를 명시적으로 변화시켜 라벨 생성 비용 (시뮬레이션 단계/실제 시간) 과 최종 테스트 성능 (상대 백분율 편차, RPD) 사이의 파레토 프론티어를 매핑합니다.

주요 기여

• 보수적 선택 프레임워크: 본 논문은 높은 확신 없이는 학습된 선택기가 강력한 고정 규칙을 포기하지 않도록 보장하여, 공격적 최적화보다 신뢰성을 우선시하는 게이트 메커니즘을 제안합니다.
• 후회 기반 감독: 절대적 makespan 대신 상태별 후회를 사용하여, 이 방법은 부분 스케줄에서의 의사 결정에 더 강건한 로컬 규칙 순위에 집중합니다.
• 명시적 비용 - 품질 분석: 많은 연구들이 라벨 생성을 고정된 전처리 단계로 취급하는 것과 달리, 본 연구는 롤아웃 깊이와 폭을 체계적으로 변화시켜 비용 - 품질 트레이드오프를 정량화하며, 배포 예산에 대한 실용적인 지침을 제공합니다.
• CPU 만 재현 가능성: 라벨 생성, KNN 피팅, 추론을 포함한 전체 파이프라인은 GPU 가속 없이 CPU 에서 실행되도록 설계되어, 딥 강화 학습 접근법과 대조를 이룹니다.

실험 결과
실험은 $6\times6$, $10\times10$, $15\times10$ 크기의 합성 JSSP 인스턴스에서 수행되었습니다.

• 성능: 후회 게이트 선택기는 모든 규모에서 학습된 모든 방법 중 가장 낮은 평균 RPD 를 달성했습니다. 이는 일반적으로 합성 설정에서 FIFO 또는 MOPNR 인 최상의 고정 디스패칭 규칙과 매우 근접하게 유지되었으며, 평균 RPD 격차는 각각 0.70, 0.67, 0.06 이었습니다.
• 강건성: 게이트 접근 방식은 Random-HH 기준선의 평균 RPD 를 한 자리 수 이상으로 감소시켰습니다 (~36–54% 에서 ~0.8–2.8% 로).
• 절대 분석: 연구는 게이트가 항상 전환 (argmin 선택) 하는 것보다 더 안정적임을 확인했습니다. 최상의 결과는 후회 라벨과 신뢰 임계값 $\lambda=1.0$으로 얻어졌습니다. 하한 신뢰 구간 (LCB) 변형은 더 나쁜 성능을 보였으며, 이는 불확실성이 직접적인 점수 보너스보다는 전환 테스트로 사용하는 것이 더 좋음을 시사합니다.
• 비용 분석: 완전한 롤아웃 ($\kappa=\infty, b=|H|$) 은 최고의 품질을 제공했지만 가장 높은 비용이 들었습니다. 얕은 롤아웃 ($\kappa=1$) 은 유의미하게 높은 RPD 를 초래했습니다. 중간 깊이는 시뮬레이션 단계를 크게 줄이면서 수용 가능한 품질을 유지하는 실현 가능한 트레이드오프를 제공했습니다.

의의 및 주장
본 논문은 학습 기반 하이퍼휴리스틱에서 라벨 비용과 보수적 전환을 연구하기 위한 재현 가능하고 CPU 만 사용하는 선택기 및 평가 프로토콜을 제공한다고 겸손하게 주장합니다.

저자들은 그들의 작업을 전문 솔버, 딥-RL 디스패처 (예: L2D, ScheduleNet), 그리고 LLM 기반 프로그램 검색 (예: FunSearch, ReEvo) 과 보완적인 것으로 위치시킵니다. 이러한 시스템들은 종종 새로운 연산자나 엔드투엔드 정책을 발명하는 등 설계 공간의 다른 지점을 목표로 하는 반면, 이 작업은 기존의 해석 가능한 규칙들 사이에서 선택하는 문제를 격리합니다.

주요 의의는 실제 배포 과제를 해결하는 데 있습니다: 라벨을 생성하기 위해 얼마나 많은 시뮬레이션 예산을 사용해야 하며, 학습된 선택기가 너무 자주 전환하여 성능을 저하시키지 않도록 어떻게 보장할 것인가입니다. 저자들은 그들의 발견이 테스트된 합성, 정적, 결정론적 영역에 국한됨을 지적합니다. 산업 인스턴스나 동적 환경 (예: 기계 고장, 온라인 도착) 으로 확장하려면 다른 비용 - 품질 트레이드오프와 잠재적으로 다른 라벨 생성 역학이 필요할 것이라고 인정합니다. 이 작업은 JSSP 를 일반적으로 해결한다고 주장하지는 않지만, 학습 기반 하이퍼휴리스틱을 신뢰할 수 있고 비용 효율적으로 만드는 것에 대한 통제된 연구를 제공합니다.