💻 computer science

Machine Learning-Based Waiting Time Prediction for Priority Queues with Preemptive and Non-Preemptive Service Rules

이 논문은 머신러닝 모델, 특히 순환 신경망(Recurrent Neural Networks)이 대기열 길이와 고객 우선순위만을 사용하여 복잡하고 시변적인 우선순위 큐잉 시스템에서의 대기 시간을 정확하게 예측할 수 있음을 입증하며, 비선점 및 다양한 선점 서비스 규칙 전반에 걸쳐 트리 기반 방식보다 우수한 성능을 보임을 보여준다.

원저자: Sahil Singh Bhandari, T.G. Deepak

게시일 2026-06-29

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Sahil Singh Bhandari, T.G. Deepak

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 지금 테마파크의 북적이는 줄 안에 서 있다고 상상해 보세요. 보통은 "선착순"이라는 규칙이 적용됩니다. 하지만 이 논문에서 저자들은 VIP(우선순위 1)와 일반 고객(우선순위 2)이 섞여 있는 더 복잡한 줄을 살펴봅니다. VIP들이 줄 중간에 끼어들면서 다른 사람들의 대기 시간이 어떻게 변하는지를 말이죠.

저자들이 던진 핵심 질문은 이것입니다: 컴퓨터 프로그램(머신러닝)을 사용하여, 줄이 혼란스럽고 VIP들이 계속 끼어드는 상황에서도 한 사람이 정확히 얼마나 기다릴지 예측할 수 있을까?

다음은 그들이 무엇을 했고 무엇을 발견했는지 일상적인 비유를 들어 쉽게 풀어낸 내용입니다.

줄의 세 가지 규칙

저자들은 줄이 작동하는 세 가지 서로 다른 "도로 규칙" 아래에서 컴퓨터 프로그램들을 테스트했습니다.

"중단 없음" 규칙 (Non-Preemptive): 미용사가 손님의 머리를 자르고 있는 상황을 상상해 보세요. VIP가 들어오더라도 미용사는 현재 진행 중인 커트를 마친 후에 교체합니다. 의자에 앉아 있는 사람은 그대로 유지됩니다.
"처음부터 다시" 규칙 (Preemptive-Repeat): 요리사가 스테이크를 굽고 있는 상황을 상상해 보세요. 만약 VIP가 도착하면, 요리사는 일반 고객의 스테이크 요리를 멈추고, 그것을 버린 뒤 VIP를 위해 새 스테이크를 처음부터 다시 만들기 시작합니다. VIP가 끝난 후에야 일반 고객은 자신의 스테이크를 처음부터 다시 시작해야 합니다.
"일시 정지 후 재개" 규칙 (Preemptive-Resume): 비디오 게임 캐릭터가 보스와 싸우고 있는 상황을 상상해 보세요. 만약 VIP가 도착하면, 전투가 일시 정지됩니다. 일반 고객의 "체력 바"는 정확히 그 자리에 그대로 남아 있습니다. VIP가 떠나면, 전투는 멈췄던 지점에서 바로 다시 시작됩니다.

데이터: 200일간의 시뮬레이션

실제 줄에서 200일을 기다리며 테스트할 수는 없었기에, 그들은 디지털 시뮬레이션을 구축했습니다. 그들은 다음과 같은 가상의 세계를 만들었습니다:

사람들이 무작위 시간으로 도착합니다 (때로는 줄이 비어 있고, 때로는 인파로 가득 찹니다).
두 종류의 사람이 있습니다: VIP와 일반 고객.
그들은 이 시뮬레이션을 200 "일" 동안 실행하여, 누가 얼마나 기다렸는지에 대한 방대한 데이터를 생성했습니다.

콘테스트: 다섯 가지 컴퓨터 두뇌

그들은 다섯 가지 유형의 "컴퓨터 두뇌"(머신러닝 모델)를 서로 맞붙여, 어떤 모델이 대기 시간을 가장 잘 예측하는지 실험했습니다.

"트리" 두뇌 (GBM & Random Forest): 이것을 일련의 "예/아니오" 질문을 던지는 탐정 팀이라고 생각하세요. "줄이 긴가? 이 사람은 VIP인가?" 그들은 의사결정 나무를 만들어 대기 시간을 추측합니다. 또한, 탐정들이 두 개의 별도 팀(VIP용과 일반 고객용)으로 나뉘도록 강제했을 때 도움이 되는지도 테스트했습니다.
"시간 여행자" 두뇌 (RNN): 이것은 순환 신경망(Recurrent Neural Network)입니다. 이것을 줄의 이야기를 기억하는 두뇌라고 생각하세요. 단순히 현재 순간만을 보는 것이 아니라, 이전에 도착했던 사람들의 순서를 기억합니다. "긴 일반 고객 줄 바로 뒤에 VIP가 도착하는 것"이 특정한 파급 효과를 일으킨다는 것을 이해합니다.

주요 발견 사항

1. "시간 여행자" 두뇌가 경주에서 승리했습니다
RNN(사건의 순서를 기억하는 모델)이 명백한 승자였습니다. 이 모델은 특히 중단이 발생하는 "처음부터 다시" 및 "재개" 규칙에서 대기 시간을 예측하는 데 가장 정확했습니다.

이유: 우선순위 줄에서 기다리는 것은 단지 '지금 당장' 일어나는 일뿐만 아니라, '방금 전'에 무슨 일이 있었고 '다음에' 무슨 일이 일어날지에 관한 것이기 때문입니다. RNN은 그 이야기를 읽어내는 데 능숙합니다.

2. "트리" 두뇌는 훌륭했지만 완벽하지는 않았습니다
의사결정 나무 모델(GBM과 Random Forest)은 준수한 성적을 냈지만, RNN만큼 날카롭지는 못했습니다. 이 모델들은 중단이 빈번하게 발생할 때 조금 더 어려움을 겪었습니다.

3. 팀을 나누는 것은 큰 도움이 되지 않았습니다
저자들은 트리 모델들이 VIP와 일반 고객을 위해 별도의 팀을 갖도록 강제하여, 모델이 더 잘 집중할 수 있는지 테스트했습니다. (이를 "강제 우선순위 분할"이라 함)

결과: 거의 차이가 없었습니다. 표준 모델들은 이미 스스로 VIP와 일반 고객의 차이를 파악할 만큼 충분히 똑똑했습니다. 팀을 나누는 것은 마치 한 명의 유능한 셰프가 두 메뉴를 모두 다룰 수 있는데도 두 명의 셰프를 고용하는 것과 같았습니다.

4. "마법의 두 가지" 입력값
이 부분이 가장 놀라운 부분입니다. 보통 대기 시간을 완벽하게 예측하려면 도착률, 서비스 속도, 시간대 등 모든 것을 알아야 합니다.

발견: 저자들은 모델이 단 두 가지 정보만으로도 대기 시간을 매우 정확하게 예측할 수 있다는 것을 발견했습니다:
1. 현재 줄에 몇 명이 있는가? (대기 행렬 길이)
2. 이 사람은 VIP인가 일반 고객인가? (우선순위)
시간대나 사람들이 보통 얼마나 빨리 도착하는지와 같은 정보를 몰라도, 단지 현재의 인파 규모와 사람의 상태만 알면 컴퓨터는 훌륭한 추측을 할 수 있었습니다.

결론

이 논문은 우선순위 줄의 대기 시간을 예측하기 위해 수백만 개의 데이터 포인트가 담긴 초복잡한 시스템이 필요하지 않다는 것을 보여줍니다.

만약 최고의 정확도를 원한다면, 사건의 순서를 기억하는 모델(RNN 같은)을 사용하십시오.
만약 단순함을 원한다면, 줄에 있는 사람 수를 세고 우선순위 배지를 확인하는 것만으로도 놀라울 정도로 좋은 결과를 얻을 수 있습니다.

이는 병원이나 콜센터와 같은 실제 시스템에 매우 좋은 소식입니다. 왜냐하면 이러한 시스템들은 도착률에 대한 완벽한 데이터를 가지고 있지 않을 때가 많지만, 대기 중인 사람이 몇 명인지와 누가 중요한지는 알고 있기 때문입니다. 그들은 이 간단한 입력값들을 사용하여 사람들에게 정확한 대기 시간 추정치를 제공할 수 있습니다.

기술 요약: 우선순위 큐를 위한 머신러닝 기반 대기 시간 예측

문제 정의

본 논문은 시변(time-varying) 조건 하에서 작동하는 다중 클래스 우선순위 큐잉 시스템의 과도적 대기 시간을 예측하는 과제를 다룹니다. 고전적인 큐잉 이론은 단순하고 정적인 시스템에 대해서는 정확한 해석적 결과를 제공하지만, 실제 응용 분야(예: 의료, 콜센터, 물류)는 종종 비정상적(non-stationary) 도착률, 복잡한 서비스 시간 분포, 그리고 선점(preemption) 규칙을 포함합니다. 이러한 환경에서 고객의 대기 시간은 현재의 큐 상태뿐만 아니라 미래의 고우선순위 도착에도 영향을 받기 때문에, 해석적인 예측이 어렵습니다.

본 연구는 머신러닝(ML) 모델이 상세한 기초 도착률 함수나 서비스 시간 분포에 대한 지식 없이도, 운영상 관찰 가능한 제한된 데이터(구체적으로 도착 시점의 큐 길이와 고객의 우선순위 클래스)만을 사용하여 대기 시간을 정확하게 예측할 수 있는지 여부를 조사합니다.

방법론

데이터 생성

저자들은 시변 환경에서의 2클래스 우선순위 큐( $G(t)/G/1$ )를 시뮬레이션하는 합성 데이터셋을 생성하여 200일간의 독립적인 일수를 시뮬레이션했습니다.

도착 프로세스: 단순 지수 분포 이상의 변동성을 포착하기 위해 위상형(Phase-Type, PH) 분포를 사용하여 구간별로 균일한(piecewise-homogeneous) 간격을 통해 비정상적 도착을 모델링했습니다.
서비스 규율: 세 가지 뚜렷한 서비스 규칙을 시뮬레이션했습니다:
1. 비선점(Non-Preemptive): 일단 시작되면 서비스가 중단 없이 계속됩니다.
2. 선점-재시작(Preemptive-Repeat): 고우선순위 도착이 저우선순위 작업을 중단시키며, 중단된 작업은 재개 시 처음부터 다시 시작해야 합니다.
3. 선점-재개(Preemptive-Resume): 고우선순위 도착이 저우선순위 작업을 중단시키지만, 작업은 중단된 지점부터 재개됩니다.
특성(Features): 두 가지 특성 구성이 테스트되었습니다:
1. 4개 특성 세트: 도착 시간, 도착 간격 시간, 우선순위 클래스, 도착 시 큐 길이.
2. 2개 특성 세트: 우선순위 클래스와 도착 시 큐 길이만 포함.

평가된 모델

다섯 가지 머신러닝 모델을 비교했습니다:

그래디언트 부스팅 머신(GBM): 결정 트리 기반의 표준 앙상블 모델입니다.
강제 우선순위 분할 GBM (FS-GBM): 학습 전 데이터셋을 우선순위 클래스별로 강제로 분할하는 변형 모델입니다.
랜덤 포레스트(RF): 상관관계가 낮은 결정 트리들의 표준 앙상블입니다.
강제 우선순위 분할 RF (FS-RF): 각 우선순위 클래스에 대해 별도로 학습된 RF 모델을 사용하는 변형 모델입니다.
순환 신경망(RNN): 하루 동안의 고객 도착 시퀀스 내의 시간적 의존성을 포착하도록 설계된 LSTM 기반 아키텍처입니다.

성능은 평균 절대 오차(MAE), 평균 제곱 오차(MSE), 평균 제곱근 오차(RMSE), 그리고 결정 계수( $R^2$ )를 사용하여 평가되었습니다.

주요 기여

통합 프레임워크: 본 연구는 비선점, 선점-재시작, 선점-재개의 서비스 규율과 시변 도착을 아우르는 과도적 데이터를 생성하기 위한 통합 시뮬레이션 프레임워크를 제공합니다.
우선순위 인지 구조의 평가: 우선순위를 하나의 특성으로 취급하는 표준 모델과 비교하여, 데이터를 우선순위 클래스별로 강제 분할하는 것(FS-GBM, FS-RF)이 예측 성능을 개선하는지 명시적으로 테스트합니다.
최소 정보의 실현 가능성: 본 연구는 두 개의 입력값(큐 길이와 우선순위)만으로도 정확한 대기 시간 예측이 가능하다는 것을 입증하며, 데이터 기반 접근 방식에 상세한 시스템 파라미터가 반드시 필요하다는 가설에 도전합니다.
비교 분석: 우선순위 큐잉 맥락에서 트리 기반 앙상블 모델과 시퀀스 기반 딥러닝 모델 간의 포괄적인 비교를 제공합니다.

결과

모델 성능

RNN의 우월성: 순환 신경망(LSTM)은 세 가지 서비스 규율과 두 가지 특성 설정 모두에서 일관되게 가장 높은 정확도를 달로했습니다. 이는 특히 서비스 중단이 복잡한 의존성을 만드는 선점 상황에서 복잡한 시간적 역학을 모델링하는 능력을 보여주었습니다.
- 비선점 설정(4개 특성)에서 RNN은 약 0.94의 결정 계수를 보인 트리 기반 모델에 비해 0.987의 $R^2$ 를 달성했습니다.
- 가장 복잡한 시나리오인 선점-재개 설정에서, 트리 기반 모델이 약 0.927로 하락한 반면, RNN은 0.987의 $R^2$ 를 유지했습니다.
트리 기반 모델의 안정성: GBM과 랜덤 포레스트 모델은 특히 비선점 설정에서 안정적이고 경쟁력 있는 성능을 제공했습니다. 그러나 선점 시나리오에서는 RNN에 비해 정확도가 감소하는 모습을 보였습니다.
강제 분할의 비효효율성: "강제 우선순위 분할" 변형 모델(FS-GBM 및 FS-RF)은 표준 모델에 비해 미미하고 일관되지 않은 개선만을 제공했습니다. 저자들은 표준 트리 기반 모델이 우선순위가 입력 특성으로 포함될 때 이미 우선순위별 비선형성을 암묵적으로 학습할 수 있으므로, 명시적인 강제 분할이 불필요하다고 결론지었습니다.

특성 축소

입력 특성을 4개에서 2개(도착 시간 및 도착 간격 시간 제거)로 줄였을 때 성능 저하는 완만했습니다.

RNN은 최소한의 입력만으로도 강력한 예측력을 유지하여, 비선점의 경우 $R^2$ 0.974, 선점-재개의 경우 $R^2$ 0.972를 달성했습니다.
트리 기반 모델 또한 안정성을 유지하여, 큐 길이와 우선순위가 필요한 예측 정보의 대부분을 인코딩하고 있음을 시사했습니다.

의의 및 주장

본 논문은 머신러닝, 특히 RNN과 같은 시퀀스 기반 모델이 우선순위 기반 서비스 시스템의 실시간 대기 시간 예측을 위한 실용적이고 강력한 대안을 제공한다고 주장합니다.

실제 적용 가능성: 정확한 예측이 큐 길이와 우선순위라는 두 가지 요소만으로 가능하다는 발견은 매우 중요한 실무적 이점으로 강조됩니다. 병원이나 콜센터와 같은 많은 실제 시스템에서 상세한 도착률 함수나 서비스 분포는 알려져 있지 않거나 추정하기 어렵지만, 큐 길이와 우선순위는 쉽게 관찰할 수 있습니다.
선점 처리: 본 연구는 ML 모델이 명시적인 중단 로직 모델링 없이도 선점(재시작 및 재개 모두)의 복잡한 효과를 효과적으로 포착할 수 있음을 입증합니다. 이는 분석적으로 매우 까다로운 작업입니다.
모델 선택: 선점 시스템의 시간적 역학을 포착하는 데는 RNN이 가장 효과적이지만, 해석 가능성이나 더 단순한 아키텍처를 선호하는 경우 트리 기반 모델 또한 신뢰할 수 있고 안정적이며 계산 효율적인 대안이 될 수 있습니다.
구조적 수정의 한계: 본 논문은 명시적으로 우선순위 분할을 강제하는 것이 성능을 크게 향cap하지 않는다는 점을 겸허히 결론지으며, 이는 현대의 앙상블 방법론이 표준적인 특성 포함을 통해 우선순위 이질성을 충분히 처리할 수 있을 만큼 견고함을 시사합니다.

저자들은 본 연구가 고전적인 큐잉 이론과 현대적인 데이터 기반 예측 사이의 가교 역할을 하며, 데이터 가용성이 제한적이고 동적인 운영 조건에 처한 시스템에 적합한 프레임워크를 제공한다고 강조합니다.