기술 요약: DynaSchedBench

문제 제기

동적 유연 작업장 스케줄링 문제 (DFJSP) 에 대한 신경 결합 최적화 (NCO) 분야는 진전을 방해하는 방법론적 긴장감에 직면해 있습니다. 기존 정적 벤치마크 (예: Taillard, DMU) 는 에이전트가 일반화 가능한 정책을 학습하는 대신 특정 인스턴스 구조를 암기하도록 유도하여 과적합을 조장합니다. 반면, 동적 인스턴스를 생성하려는 시도는 종종 보정되지 않은 절차적 샘플링에 의존하며, 여기서 난이도는 무작위 시드의 통제되지 않은 부산물로 나타납니다. 이는 고분산 "확률적 안개"를 초래하여, 진정한 알고리즘적 혁신과 유리한 동적 사건들의 순서를 구별하는 것을 불가능하게 만듭니다. 더 나아가, 스케줄링 에이전트로서 대규모 언어 모델 (LLM) 의 등장은 통제되고 분포적으로 타당한 환경에서 기존 솔버에 대한 추론 능력을 테스트할 엄격한 평가 프레임워크가 부재합니다.

방법론: DynaSchedBench 프레임워크

저자들은 DFJSP 를 위해 보정되고 이론적으로 근거한 벤치마크 인스턴스를 생성하도록 설계된 진단 프레임워크인 DynaSchedBench를 소개합니다. 이 프레임워크는 네 가지 핵심 구성 요소로 이루어져 있습니다:

1. 순차적 이벤트 공간 보정기 (SESC)

DynaSchedBench 는 계산 비용이 많이 들고 불안정성이 따르는 매개변수 공간에서 생성적 하이퍼파라미터를 최적화하는 대신 SESC 를 사용합니다. 이 모듈은 실현된 이산 이벤트 스트림 $E$에서 직접 작동합니다. 이는 이벤트 스트림을 목표 지표와 일치하도록 조정하기 위해 일련의 국소 구조 변환 (연산자) 을 적용합니다.

• 조정 전략: 프레임워크는 도착 구조 조정 (율 보정, 갱신 재샘플링), 적응적 유휴 시간 스케일링 (납기일 엄격도 수정), 동형 처리 시간 재샘플링 (전체 작업량을 유지하면서 변동성 보정), 그리고 병목 엔지니어링 (용량 손실에 대한 세밀한 제어) 을 포함한 전략 카탈로그를 활용합니다.
• 보정 루프: 탐욕적 탐색은 관측된 지표와 목표 지표 간의 정규화된 오차 벡터를 최소화하면서 이미 허용 오차 내에 있는 지표들을 유지하는 연산자를 선택합니다.

2. 스케줄 스트레스 지수 (SSI)

인스턴스 난이도를 정량화하기 위해 저자들은 **스케줄 스트레스 지수 (SSI)**를 제안합니다. 이 지표는 원시 경험적 지표를 네 가지 구성 요소로 이루어진 난이도 벡터로 매핑합니다:

• 혼잡도 ($C$): 킹먼 스타일의 혼잡 트래픽 근사를 기반으로 하며, 자연스러운 병목 활용률과 변동성을 활용합니다.
• 시간 압박 ($P$): 경험적 유휴 시간의 역수입니다.
• 구조적 복잡성 ($K$): 기계 수와 작업 깊이의 정규화된 측정치입니다.
• 교란 강도 ($S$): 실현된 교란 비율 (예: 고장) 의 정규화된 측정치입니다.
  이러한 구성 요소들은 로그 압축되어 평균화되어 스칼라 난이도 점수 $d \in [0, 100]$을 생성합니다.

3. 모듈식 시뮬레이션 및 평가 스택

이 프레임워크는 다음을 갖춘 Gym 호환 환경을 제공합니다:

• 스냅샷 기반 시뮬레이션: 에이전트를 위한 불변 관측치를 보장하여 메모리 없는 정책과 룩어헤드 플래너 모두를 지원합니다.
• 궤적 기반 엔진: 재현 가능한 제약 조건 검증 (선후행 관계, 자원 중첩 없음) 및 성능 지표 계산을 위해 실행 흔적을 유지합니다.
• 관측성 수준: 에이전트용 정보 접근의 세 가지 수준을 정의합니다:
  • L1: 로컬 뷰 (준비된 작업, 기계 가용성).
  • L2: L1 + 로컬 통계 (대기열 길이, 유휴 시간 계수).
  • L3: L2 + 구조적 사전 지식 (병목 점수, 설계 목표).

4. LLM 에이전트 평가

이 프레임워크는 다양한 프롬프팅 모드 (직접, 사고의 사슬, 도구 증강) 와 정제 전략 (반성, Best-of-N) 을 사용하여 LLM 기반 에이전트를 평가합니다. 이는 관측된 최상의 스케줄에 대한 정규화된 최대 완료 시간 ($C_{max}$) 을 통해 성능을 측정하고, 토큰 소비를 추적하여 비용 - 성능 트레이드오프를 평가합니다.

주요 결과

보정 성능

• 효율성 및 안정성: SESC 는 계산 효율성과 안정성 측면에서 진화적 베이스라인 (다목적 최적화 및 하이브리드 접근법) 을 크게 능가합니다. SESC 는 중앙값 보정 실행 시간을 0.2 초로 달성한 반면, MOO 는 57.9 초, 하이브리드는 185.8 초였습니다.
• 정확도: SESC 는 베이스라인에 비해 더 낮은 평균 정규화된 손실 ($\tilde{\ell}_2 \approx 0.0539$) 과 최소의 시드 간 분산을 보여주어 우수한 알고리즘적 안정성을 입증했습니다.
• 난이도 상관관계: SSI 점수는 무작위 스케줄러와 최상의 고정 휴리스틱 간의 스케줄링 갭과 양의 상관관계 ($\rho = 0.563$) 를 보여, 스케줄링 난이도의 대리 지표로서의 유용성을 검증합니다.

LLM 스케줄링 발견

• 관측성 역설: 에이전트에 완전한 구조적 사전 지식 (L3) 을 제공하는 것은 간결한 통계 요약 (L2) 에 비해 성능을 저하시킵니다. L2 CoT 에이전트는 평균 정규화된 초과 최대 완료 시간 0.7% 를 달성한 반면, L3 CoT 에이전트는 1.66% 로 저하되었습니다. 이는 현재 LLM 이 고차원 구조적 노이즈에서 유용한 신호를 추출하는 데 어려움을 겪고 있음을 시사합니다.
• 능동적 프로빙의 비효율성: 도구 증강 전략 (L1+Tool) 은 표준 L1 CoT 대비 성능 향상 없이 토큰 소비를 세 배 증가시켜 "정보 통합 병목"을 부각시켰습니다.
• 휴리스틱 동등성: 상당한 토큰 오버헤드와 고급 추론 전략 (반성, Best-of-N) 이 있음에도 불구하고, LLM 은 강력한 수동 제작 우선순위 배정 규칙 (PDR) 을 일관되게 능가하지 못합니다. 최상위 LLM(예: Qwen3-8B) 은 최상의 고정 휴리스틱 (예: LIFO+LIT) 과 통계적으로 구별되지 않게 수행되어, 이를 최상의 최적화자가 아닌 견고한 휴리스틱 근사기로 특징짓습니다.

중요성 및 주장

이 논문은 분포적으로 통제된 벤치마크를 생성하기 위한 원칙 있는 프레임워크를 제공함으로써 동적 스케줄링의 평가 위기를 해결한다고 주장합니다. 그 주요 중요성은 다음과 같습니다:

1. 방법론적 엄밀성: 인스턴스 난이도의 체계적 계층화를 가능하게 하는 결정론적 이벤트 공간 보정 프로세스로 보정되지 않은 샘플링을 대체합니다.
2. 진단적 통찰: 결합 문제에서 LLM 기반 에이전트의 의사결정을 위해 더 많은 정보 (구조적 사전 지식) 가 더 나은 결과를 가져온다는 가정에 도전하는 "관측성 역설"을 밝혀냅니다.
3. 현실적인 기대: 현재 LLM 이 고급 프롬프팅과 도구 사용을 하더라도 주로 고전적 휴리스틱의 견고한 근사기로 작용하며 변혁적 최적화자는 아니라는 점을 확립하여, 반응형 배치가 아닌 다단계 궤적 계획으로 연구 방향을 전환할 필요성을 시사합니다.

저자들은 이러한 보정된 환경 없이는 신흥 에이전트의 추론 능력을 신뢰할 수 있게 벤치마크할 수 없으며, 현재 세대의 LLM 은 동적 스케줄링 맥락에서 고전적 휴리스틱의 성능 한계로 제한된다고 결론지었습니다.