Dynamic Scheduling of a Parallel-Server Queueing System: A Computational Method for High-Dimensional Problems

기술 요약: 병렬 서버 대기 행렬 시스템의 동적 스케줄링

문제 정의
본 논문은 콜센터와 같은 대규모 병렬 서버 대기 행렬 시스템에서의 기술 기반 라우팅 운영 과제를 다룹니다. 핵심 문제는 대기 중인 고객 클래스 중 어떤 클래스를 가용한 어떤 에이전트가 서비스해야 하는지에 대한 실시간 의사결정입니다. 많은 수의 고객 클래스와 서비스 스테이션이 있는 시스템에서는 상태 공간이 고차원이 되어, 차원의 저주로 인해 표준 동적 프로그래밍 방법이 계산적으로 처리 불가능해집니다. 저자들은 Halfin-Whitt 과부하 체제와 무한 시간 범위 할인 비용 기준에 초점을 맞추어, 이러한 고차원 설정을 위한 확장 가능한 계산 방법을 개발하는 데 주력합니다.

방법론
제안된 접근법은 이론적 과부하 한계와 실용적 계산 사이의 간극을 다음 단계들을 통해 메웁니다:

1. 확산 근사: 저자들은 Halfin-Whitt 점근 체제 하에서 원래의 이산 흐름 대기 행렬 모델에서 유도된 근사 브라운 제어 문제 (BCP) 를 수립합니다. 이는 시스템 상태와 제어 과정을 스케일링하여 확률 미분 방정식에 의해 지배되는 한계 확산 과정을 유도하는 것을 포함합니다.
2. 해밀턴 - 자코비 - 벨만 (HJB) 공식화: BCP 에 대한 최적 제어 문제는 준선형 편미분 방정식 (PDE), 구체적으로 HJB 방정식으로 특징지어집니다. 이 PDE 의 해는 최적 정책을 구성하는 데 필요한 가치 함수와 그 기울기를 제공합니다.
3. 딥러닝 기반 솔루션: 전통적인 수치 방법 (예: 유한 요소 방법) 이 고차원에서 실패한다는 점을 인식하여, 저자들은 준선형 PDE 를 해결하기 위해 Han 등 (2018) 의 딥러닝 프레임워크를 적용합니다.
   • 확률적 항등식: 그들은 HJB 방정식과 동등한 특정 확률적 항등식 (명제 1) 을 유도합니다. 이 항등식은 가치 함수와 그 기울기를 역방향 확률 미분 방정식 (BSDE) 표현을 통해 시스템의 드리프트, 확산, 비용 항과 연결합니다.
   • 신경망 근사: 가치 함수 $V(x)$와 그 기울기 $\nabla V(x)$는 심층 신경망으로 근사됩니다.
   • 손실 함수: 기준 정책의 시뮬레이션된 표본 경로에서의 유도된 확률적 항등식의 불일치에 기반하여 손실 함수가 구성됩니다. 네트워크 매개변수는 이 손실을 최소화하기 위해 확률적 경사 하강법을 사용하여 최적화됩니다.
   • 정책 구성: 기울기 네트워크가 훈련되면, 원래 (예비 한계) 시스템에 대한 정책은 각 상태에서 선형 프로그래밍을 풀어 구성됩니다. 이 선형 프로그래밍은 학습된 기울기 값을 계수로 사용하여 HJB 방정식의 상한에서 유도된 항을 최대화합니다.

주요 기여

• 확장 가능한 계산 프레임워크: 주요 기여는 표준 MDP 기법이 불가능한 고차원 병렬 서버 시스템 (최대 100 개의 고객 클래스) 의 동적 스케줄링 문제를 해결할 수 있는 계산 방법입니다.
• 비기본 활동 처리: "기본" 활동으로 분석을 제한하고 공동 작업 보존 (JWC) 을 가정하는 이전 이론적 연구 (예: Atar, 2005a) 와 달리, 이 방법은 비기본 활동이 활용될 수 있고 JWC 가 성립하지 않을 수 있는 일반적인 병렬 서버 네트워크를 수용합니다.
• 데이터 기반 보정: 이 방법은 미국 내 대형 은행 콜센터의 실제 데이터를 사용하여 보정 및 테스트되었으며, 도착률, 서비스률, 포기율, 비용 구조를 포함한 현실적인 운영 매개변수를 반영하도록 테스트 사례가 구성되었습니다.
• 도메인 지식 통합: 이 접근법은 대표성 있는 표본 경로를 생성하고 가치 함수 및 그 기울기에 형태 제약을 부과하는 것과 같은 도메인 특화 통찰력을 통합하여 해의 품질을 향상시킵니다.

결과
저자들은 제안된 정책을 여러 테스트 문제에서 벤치마크 정책 ($c\mu$, $c\mu/\theta$, Fastest-Server-First, G-$c\mu$ 규칙 포함) 과 비교 평가했습니다:

• 저차원 문제: 표준 MDP 기법으로 최적 정책을 계산할 수 있는 2 차원 테스트 문제의 경우, 제안된 신경망 기반 정책은 최적 정책과 동등한 성능을 발휘하며, 최적성 격차는 1% 미만입니다.
• 고차원 문제: 최적 정책이 알려지지 않은 주요 13 차원 테스트 문제 (은행 데이터 기반) 와 100 차원 테스트 문제에서, 제안된 정책은 항상 가장 우수한 벤치마크보다 일관되게 우수한 성과를 냅니다.
  • 13 차원 변형에서 제안된 정책은 가장 우수한 벤치마크 대비 약 2% 의 성능 개선을 보였습니다.
  • 100 차원 문제에서는 가장 우수한 벤치마크 대비 약 7% 의 개선이 있었습니다.
• 행동적 통찰: 이 연구는 희소 네트워크 토폴로지에서는 최적 정책이 공동 작업 보존 속성을 위반하고 비기본 활동을 상당히 활용할 수 있음을 보여줍니다. 제안된 방법은 이러한 행동을 자연스럽게 포착하는 반면, 정책을 기본 활동으로 제한하거나 JWC 를 강제하는 것은 최적 전략을 배제할 수 있습니다.

의의 및 주장
본 논문은 정확한 방법으로 처리하기에는 너무 큰 고차원 서비스 시스템을 관리하기 위한 확장 가능하고 데이터 기반의 계산 프레임워크를 제공한다고 주장합니다. 이는 관리자에게 실시간 라우팅 의사결정을 개선하고 구현 전에 정책을 평가할 수 있는 도구를 제공합니다. 저자들은 자신의 작업을 기존 문헌의 중요한 일반화로 위치지으며, 저차원적이고 제한적인 이론적 모델에서 고차원적이고 실용적인 응용으로의 이동을 강조합니다. 그들은 공동 작업 보존을 가정하거나 활동을 "기본" 집합으로 제한하지 않는 그들의 방법이 복잡하고 다양한 서비스 시스템을 더 유연하고 잠재적으로 더 정확하게 표현한다고 강조합니다. 논문은 제안된 접근법이 100 개 이상의 서로 다른 고객 클래스를 가진 시스템에 대해 계산적으로 실현 가능하며, 이는 이전에는 이러한 맥락에서 동적 최적화를 달성할 수 없었던 규모라고 결론지었습니다.