🔢 mathematics

Near-optimal scheduling with general service times and IHR abandonment times

본 논문은 일반적인 서비스 시간과 IHR 포기 시간을 갖는 M/G/N 대기 행렬에서의 동적 스케줄링 문제를 다루며, 관련 이산 시간 문제의 인덱스 가능성(indexability)을 증명하고, 명시적인 휘틀 지수(Whittle index)를 도출하며, 시뮬레이션을 통해 결과적인 정책이 표준 $c\mu/\theta$ -규칙보다 체계적으로 우수한 성능을 보임을 입증한다.

원저자: Samuli Aalto

게시일 2026-07-28

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Samuli Aalto

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

바쁜 커피숍을 상상해 보세요. 손님들이 음료를 받기 위해 줄을 서 있는데, 여기에는 반전이 있습니다. 모든 손님에게는 비밀 타이머가 있습니다. 만약 너무 오래 기다리면, 그들은 좌절하여 아무것도 사지 않고 떠나버립니다. 바리스타(서버)들은 다음에 누구를 응대할지 결정해야 합니다. 가장 오래 기다린 사람을 먼저 응대해야 할까요? 아니면 빠르게 에스프레소만 마시고 나갈 사람을 먼저 응대해야 할까요? 아니면 지금 당장 포기하고 떠나버릴 것 같은 사람을 먼저 응대해야 할까요? 이것이 바로 "스케줄링(scheduling)"이라 불리는 문제의 핵심입니다. 스케뮬링은 자원이 한정되어 있고 시간이 촉박할 때 작업을 최적의 방법으로 조직하는 방법을 다루는 수학 및 컴퓨터 과학의 한 분야입니다.

스케줄링의 세계에서는 두 가지 주요 비용을 고려해야 합니다. 첫째는 "보유 비용(holding cost)"으로, 이는 고객이 줄에서 기다리는 동안 소모되는 에너지와 인내심과 같습니다. 둘째는 "포기 패널티(abandonment penalty)"로, 이는 고객이 화가 나서 떠날 때 발생하는 매출 손실과 평판 저하를 의미합니다. 수십 년 동안 수학자들은 이 퍼즐을 풀기 위해 노력해 왔지만, 대개 큰 단순화를 적용했습니다. 그들은 서비스 시간(음료를 만드는 데 걸리는 시간)과 인내 시간(고객이 기다리는 시간)이 "지수 분포(exponential distribution)"라는 단순하고 예측 가능한 패턴을 따른다고 가정했습니다. 이는 마치 모든 동전 던지기가 완벽하게 무작위적이고 독립적이라고 가정하는 것과 같습니다. 이렇게 하면 수학 계산은 쉬워지지만, 실제 현실을 반영하지는 못합니다. 실제로는 어떤 작업은 매우 오래 걸리고, 어떤 사람은 믿기지 않을 정도로 인내심이 강하거나 혹은 매우 조급할 수 있기 때문입니다.

샘 훌리 알토(Samuli Aalto)가 작성한 이 논문은 이 문제의 복잡하고 현실적인 버전을 다룹니다. 저자는 단순하고 예측 가능한 패턴을 가정하는 대신, 어떤 종류의 서비스 시간(예: 엄청 오래 걸리는 복잡한 라떼)도 허용하며, 특정 유형의 조급함인 "IHR(Increasing Hazard Rate, 증가하는 위험률)"을 적용합니다. IHR은 사람이 기다리는 시간이 길어질수록 더 화가 나서 떠날 가능성이 높아진다는 것을 의미하는 세련된 표현으로, 실제 인간의 행동 방식과 같습니다. 이 논문은 사람들이 다음에 누구를 응대할지 결정하기 위해 "휘틀 지수(Whittle index)"라는 영리한 수학적 도구를 사용합니다. 이 새로운 방법은 기존의 표준적인 규칙( $c\mu/\theta$ 규칙)보다 일관되게 우수한 성능을 보인다는 점을 컴퓨터 시뮬레이션을 통해 입증했습니다. 저자는 단순화된 버전의 문제에 대해 이 새로운 공식이 수학적으로 타당함을 증명한 후, 시뮬레이션을 통해 이 방법이 이전의 최선책들보다 더 많은 돈을 아끼고 더 많은 고객을 만족시킨다는 것을 보여줍니다.

조급한 줄의 이야기

혼란스러운 공항 보안 검색대를 상상해 보세요. 당신에게는 보안 요원들(서버)과 여행객들(고객)의 흐름이 있습니다. 각 여행객에게는 두 개의 보이지 않는 시계가 돌아가고 있습니다. 하나의 시계는 그들의 서비스 시간—가방을 스캔하고 신분증을 확인하는 데 걸리는 시간—을 카운트다운합니다. 다른 시계는 그들의 인내 시간—비행기를 포기하고 집으로 돌아가기로 결정하기 전까지 기다릴 수 있는 시간—을 카운트다운합니다.

과거에 이 줄을 모델링하던 수학자들은 두 시계가 매우 특정한 "무기억(memoryless)" 방식으로 작동한다고 가정했습니다. 이는 당신이 얼마나 오래 서 있었는지와 상관없이, 다음 1분 동안 떠날 확률이 처음 도착했을 때와 똑같다고 말하는 것과 같습니다. 이것이 바로 "지수적(exponential)" 가정입니다. 수학적으로는 깔끔한 기법이지만, 실제 사람들의 행동 방식은 아닙니다. 실제로 20분을 기다렸다면, 방금 도착했을 때보다 다음 1분 안에 화를 내며 떠날 확률이 훨씬 높습니다. 이것이 논문에서 말하는 IHR(증가하는 위험률)입니다. 즉, 기다리는 시간이 길어질수록 그만두게 될 위험이 높아지는 것입니다.

저자는 또한 실제 서비스 시간이 항상 단순하지 않다는 점을 깨달았습니다. 때로는 가방 스캔이 순식간에 끝나기도 하지만, 어떤 경우에는 가방의 이상한 잠금장치 때문에 영원히 걸리기도 합니다. 이 논문은 **일반적인 서비스 시간(general service times)**을 허용합니다. 즉, 수학이 빠른 작업부터 길고 복잡한 작업까지 모든 형태의 대기 시간을 처리할 수 있도록 합니다.

마법의 공식: 휘틀 지수

그렇다면 누구를 먼저 응대할지 어떻게 결정할까요? 이 논문은 모든 사람에게 부여되는 점수판으로서 "휘틀 지수"를 소개합니다. 이 점수는 단순히 누가 오래 기다렸는지만을 보는 것이 아닙니다. 다음과 같은 요소들을 고려한 복잡한 계산입니다:

그들이 이미 얼마나 기다렸는가(x).
그들이 이미 얼마나 많은 서비스를 받았는가(y).
그들을 계속 기다리게 함으로써 발생하는 비용(보유 비용).
그들이 떠날 경우 발생하는 비용(포기 패널티).

저자는 이 문제의 단순화된 버전(새로운 사람이 도착하지 않는 "폐쇄형" 시스템)에 대해 이 점수판이 수학적으로 완벽하다는 것을 증명합니다. 이 지수는 "지금 당장 나를 응대해 줘!"부터 "조금 더 기다릴 수 있어"까지 사람들의 순위를 매길 수 있는 "지표화 가능성(indexable)"을 갖추고 있습니다.

그 후, 논문은 이 점수판을 사람들이 끊임없이 도착하는 실제 연속적인 세상에 맞게 조정합니다. 그 결과물인 $W_k(x, y)$ 공식은 보기에는 다소 위협적일 수 있지만, 본질적으로 다음과 같이 묻습니다: "만약 내가 이 사람을 아주 짧은 시간 동안 응대한다면, 그들이 떠날 위험과 비교했을 때 얼마나 많은 돈을 아낄 수 있는가?"

대결: 신규 vs 구형

이 새로운 "휘틀 지수 정책(WHI)"이 실제로 효과가 있는지 확인하기 위해, 저자는 수천 번의 컴퓨터 시뮬레이션을 실행했습니다. 저자는 두 가지 유형의 여행객이 있는 가상의 공항을 설정했습니다:

클래스 1: 짧은 작업(빠른 스캔)이지만 인내심 수준은 다양함.
클래스 2: 긴 작업(복잡한 스캔)이며 인내심 수준이 다름.

저자는 서비스 시간의 유형(어떤 것은 균등 분포, 어떤 것은 몇몇 사람이 영원히 걸리게 만드는 "파레토(Pareto)" 분포)과 포기 비용(고객을 잃는 것이 저렴할 때도 있고, 엄청난 손실일 때도 있음)을 섞어서 네 가지 시나리오를 테스트했습니다.

결과는 명확했습니다. 새로운 휘틀 지수 정책은 기존의 표준인 $c\mu/\theta$ 규칙을 체계적으로 압도했습니다.

"균등-균등(Uniform-Uniform)" 시나리오(모두가 어느 정도 예측 가능한 경우)에서, 새로운 정책은 기존 규칙보다 약 12%에서 19% 더 많은 비용을 절감했습니다.
"균등-파레토(Uniform-Pareto)" 시나리오(일부 사람들이 매우 길고 예측 불가능한 서비스 시간을 갖는 경우)에서는 그 격차가 더 벌어졌습니다. 새로운 정책은 기존 규칙보다 33%에서 42% 더 많은 비용을 절감했습니다.
가장 까다로운 시나리오에서도 새로운 정책은 일관되게 우수했으며, 때로는 무려 **52%**까지 더 나은 성과를 보였습니다.

또한 논문은 이 새로운 방법을 "선입선출(First-Come-First-Served, 가장 오래된 사람을 먼저 응대)"이나 "프로세서 공유(Processor-Sharing, 서버의 시간을 모두에게 균등하게 배분)"와 같은 다른 일반적인 전략들과 비교했습니다. 휘틀 지수는 이 모든 전략을 물리쳤습니다.

이것이 왜 중요한가

핵심적인 교훈은, "완벽하게 무작위적"이라는 가정을 버리고 사람들이 실제로 어떻게 조급해지는지에 대한 복잡한 현실을 받아들임으로써, 훨씬 더 나은 시스템을 구축할 수 있다는 것입니다. 커피숍, 콜센터, 혹은 데이터를 처리하는 컴퓨터 네트워크든 간에, 이 새로운 공식을 사용하는 것은 더 적은 수의 화난 고객이 떠나게 하고, 낭비되는 시간을 줄이며, 더 많은 돈을 아끼는 것을 의미합니다. 저자는 단순히 추측한 것이 아니라, 단순화된 버전에서 수학적 타당성을 증명했고, 엄격한 시뮬레이션을 통해 복잡한 현실 버전에서도 놀라운 효과를 낸다는 것을 보여주었습니다. 이는 때때로 문제를 해결하는 가장 좋은 방법은 세상이 실제보다 더 단순하다고 가정하는 것을 멈추는 것임을 상기시켜 줍니다.

기술 요약: 일반적인 서비스 시간 및 IHR 이탈 시간을 갖는 근사 최적 스케줄링

문제 정의
본 논문은 이탈하는 고객이 존재하는 다중 클래스 $M/G/N$ 대기 행렬 시스템 내의 동적 스케줄링 문제를 다룹니다. 시스템은 $N$ 개의 동일한 병렬 서버와 여러 고객 클래스로 구성됩니다. 각 고객은 무작위 서비스 시간과 무작위 이탈 시간을 가집니다. 만약 고객이 이탈 시간 이후에도 시스템(대기 또는 서비스 중)에 남아 있다면, 고객은 서비스를 완료하지 못하고 떠납니다.

목표는 총 기대 비용을 최소화하는 비예측적(non-anticipating) 스케줄링 정책(선점 허용)을 결정하는 것입니다. 이 비용 함수는 두 가지 구성 요소로 이루어집니다:

유지 비용(Holding costs): 클래스- $k$ 고객이 시스템에 머무는 동안 발생하는 비용( $h_k$ ).
이탈 패널티(Abandonment penalties): 클래스- $k$ 고객이 서비스 완료 전 시스템을 이탈할 경우 발생하는 일시적 패널티( $d_k$ ).

기존 문헌은 서비스 시간과 이탈 시간 모두 지수 분포를 가정하는 경우가 많으나, 특수한 경우를 제외하고는 정확한 해를 찾기가 어렵습니다. $c\mu/\theta$ -규칙을 산출하는 유체 스케일링(fluid-scaling) 방법과 같은 기존의 근사 최적화 접근 방식들은 이러한 제한적인 지수 분포 가정에 크게 의존합니다. 본 논문은 일반적인 서비스 시간 분포와 증가 위험율(Increasing Hazard Rate, IHR) 이탈 시간을 허용함으로써 이 문제를 일반화하는 것을 목표로 합니다. IHR은 시스템에서 보낸 시간에 따라 이탈 확률이 증가한다는 자연스러운 가정입니다.

방법론
저자들은 일반적으로 수학적으로 다루기 까다로운 무력한 밴딧 문제(restless bandit problems)를 위해 설계된 휴리스틱 방법인 휘틀 인덱스(Whittle index) 접근법을 사용합니다. 방법론은 다음 단계로 진행됩니다:

이산 시간 정식화: 문제는 먼저 할인 비용(discounted costs)이 적용된 이산 시간 모델로 구축됩니다. 분석을 용이하게 하기 위해 시스템은 폐쇄형 버전(유한한 수의 고객, 새로운 도착 없음)으로 취급됩니다. 고객의 상태는 $(x, y)$ 라는 2차원 쌍으로 정의되며, 여기서 $x$ 는 시스템에서 보낸 총 시간이고 $y$ 는 달성된 서비스량입니다.
완화 및 인덱스 가능성(Indexability): 엄격한 용량 제약(최대 $N$ 명의 고객만 서비스)을 시간 평균 제약으로 완화합니다. 이를 통해 문제는 일련의 분리 가능한 하위 문제(고객당 하나)로 변환됩니다. 저자들은 이 완화된 문제가 **인덱스 가능함(indexable)**을 증명하는데, 이는 "작업의 가격" $\nu$ 에 대한 임계값(휘틀 인덱스)이 존재하여, 인덱스가 $\nu$ 보다 큰 고객을 서비스하는 것이 최적임을 의미합니다.
인덱스 유도: 2차원 상태 공간은 1차원 문제에서 발견되는 자연스러운 순서 구조가 결여되어 있어 상당한 이론적 난제가 됩니다. 저자들은 시간 지평 $\Delta$ 에 대한 극대화를 포함하는 이산 시간 설정에서의 휘틀 인덱스 $W_{k,\beta}(x, y)$ 의 명시적 표현을 유도합니다.
연속 시간 극한: 이산 시간 결과를 원래의 연속 시간 개방형 시스템으로 확장합니다. 시간 슬롯을 0으로 보내고 확률을 스케일링함으로써, 저자들은 연속 시간 휘틀 인덱스 $W_k(x, y)$ 를 도출합니다.

주요 기여

가정의 일반화: 서비스 시간에 대한 제한적인 지수 분포 가정을 제거하여 일반적인 분포를 수용하는 한편, 이탈 시간에 대해서는 IHR을 가정하였습니다.
인덱스 가능성의 이론적 증명: 저자들은 폐쇄형 이산 시간 버전의 문제가 인덱스 가능함을 증명했습니다. 이는 상태 순서에 의존하는 표준 증명과 달리, 2차원 상태 공간 $(x, y)$ 로 인해 복잡해지는 비자명한 결과입니다.
명시적 인덱스 공식: 일반적인 경우에 대해 다음과 같은 명시적 인형 식을 유도했습니다:
$W_k(x, y) = \sup_{\Delta>0} \frac{E\left[ (h_k((D_k - x) - (S_k - y)) + d_k) \mathbb{1}_{\{S_k - y < \min\{D_k - x, \Delta\}\}} \mid D_k > x, S_k > y \right]}{E[\min\{D_k - x, S_k - y, \Delta\} \mid D_k > x, S_k > y]}$
또한, 본 논문은 이 인덱스가 알려진 형태(예: 서비스 시간이 감소 위험율(DHR)인 경우 또는 이탈 시간이 지수인 경우)로 단순화되는 특정 조건들을 식별했습니다.
정책 정의: 연속 시간 설정을 위한 휘틀 인덱스 정책(WHI)이 정의됩니다. 즉, 임의의 시간 $t$ 에 스케줄러는 가장 높은 휘틀 인덱스를 가진 $N$ 명의 고객을 서비스합니다.

결과
제안된 휘틀 인덱스 정책(WHI)의 성능은 2개 클래스의 $M/G/1$ 대기 행렬에 대한 수치 시뮬레이션을 통해 잘 알려진 $c\mu/\theta$ -규칙(CMTH) 및 기타 표준 정책(FCFS, Processor-Sharing, Forward-Backward)과 비교 평가되었습니다.

체계적인 우월성: 다양한 서비스 시간 분포(Uniform/IHR 및 Pareto/DHR)와 비용 구조의 조합을 포함하는 다양한 실험 환경 전반에서, WHI 정책은 $c\mu/\theta$ -규칙 및 기타 베이스라인 정책보다 체계적으로 우수한 성능을 보였습니다.
분포 형태에 대한 민감도: 시뮬레이션은 서비스 시간이 두터운 꼬리(heavy-tailed, DHR) 분포(예: Pareto)를 따를 때 WHI와 CMTH 사이의 성능 격차가 크게 벌어짐을 보여줍니다. 이러한 시나리오에서 지수 분포를 가정하는 $c\mu/\theta$ -규칙은 상당히 열악한 성능을 보일 수 있습니다(일부 고부하 시나리오에서 상대적 비용 차이가 40-50%를 초과).
강건성(Robustness): WHI 정책은 이탈 비용이나 유지 비용 중 어느 쪽이 강조되더라도, 그리고 다양한 시스템 부하( $\rho \in [1.0, 2.0]$ )에 걸쳐 우수한 성능을 유지합니다.

의의
본 논문의 주요 의의는 더 현실적이고 복잡한 스케줄링 환경으로 휘틀 인덱스 접근법의 적용 가능성을 확장했다는 점에 있습니다. 인덱스 가능성을 증명하고 일반적인 서비스 시간 및 IHR 이탈에 대한 인덱스를 유도함으로써, 본 연구는 정확한 해를 구할 수 없는 문제들에 대해 이론적으로 근거가 있는 휴리스틱을 제공합니다. 수치적 결과는 지수 분포 가정(예: $c\mu/\theta$ -규칙)에 의존하는 것이 특히 서비스 시간이 비지수적일 때 하위 최적의 스케줄링 결정을 초래할 수 있음을 시사하며, 도출된 휘틀 인덱스 정책이 강력하고 근사 최적인 대안임을 보여줍니다.

조급한 줄의 이야기

마법의 공식: 휘틀 지수

대결: 신규 vs 구형

이것이 왜 중요한가

유사한 논문