건강 검진 스케줄링 알고리즘에 대한 연구

이 건겅검진 스케줄링 문제의 솔루션은 수검자가 원하는 검사들로 이루어진 모든 경로(Path, 조합)들의 소요시간을 추정하여, 최소 소요시간을 가지는 경로를 찾는 완전 탐색(Brute force) 방식으로 구할 수 있다. 이는 모든 경로를 조사하기 때문에 최적해(Optimal solution)를 보장한다.

병원의 총 검사실 수를 N이라 하고 검사실들을 번호 1, 2, ···, N으로 대응시키자. 이 중 수검자가 받고자 하는 검사 개수를 n이라 하고 수검자가 받고자하는 검사들의 집합을 Q라 할 때, Q ⊆ {1,2,…,N}이다.

이 때, 최적의 검진경로를 찾기 위해 검토해야 할 검진 경로는 집합 Q의 조합(Permutation)들이다. 검진 경로 P₁P₂…P_n에서 i번째 방문할 검사실의 번호를 P_i라 할 때 P_i ∈Q (i= 1, …,n)이다. 시간의 단위는 편의상 분(分)으로 설정하였고 모든 시간은 분으로 환산한다. 예를 들어, 9시 10분은 9 × 60 + 10 = 550(분)으로 숫자 550에 대응한다.

우리는 다음 최적화 문제의 해를 구함으로써 이 건강검진 문제의 솔루션을 구할 수 있다.

“수검자가 원하는 n개의 검사로 이루어진 모든 경로를 조사하여, 경로의 순서가 유효하고, 다음 식 (1)의 값을 최소로 하는 경로 P₁P₂…P_n를 구한다”

여기서, s_Pi,i는 경로 P₁P₂…P_n에서 i번째로 검사실 P_i에 도착하는 시간, w(P_i,s_Pi,i)는 시간 s_Pi,i에 검사실 P_i에 도착할 때 검사를 받기 위해 대기하는 시간(Waiting time), Δ(P_i-1,P_i)는 검사실 P_i-1에서 P_i로 이동하는데 소요되는 시간을 말한다.

의학적인 이유나 병원 사정으로 어떤 특정 검사는 다른 특정 검사보다 먼저 수행되어야 하는 경우가 있다. 예를 들어 내시경 검사는 늘 마지막에 해야 한다는 제약을 둘 수 있다. 특정 검사들의 순서에 제약을 둘 수 있는데, 우리는 이러한 제약을 모두 지킨 경로를 유효하다고 부른다. 우리는 유효한 경로 중 식 (1)을 최소로 하는 경로를 구한다.

경로 P₁P₂…P_n에서 i번째로 검사실 P_i에 도착하는 시간을 s_Pi,i라 하고 이 검사를 마치는 시간을 e_Pi,i라고 할 때 이는 <표 1>과 같이 구할 수 있다. 모든 수검자는 병원 안내데스크에서 검진을 시작하고 안내데스크를 P₀로 표기한다. e_P0,0는 안내 데스크에서 수검자 등록 시간으로 정의한다. 또, t_Pi는 검사실 P_i의 평균 진료시간, w(P_i,s_Pi,i)는 검사실 P_i에 시간 s_Pi,i에 도착 시 대기시간을 말한다. 대기시간 w의 값을 할당하는 방법은 4)절에 서 다룬다.

Table 1.

Calculation of sPi,i and ePi,i

수검자는 s_Pi,i + 1부터 e_Pi,i까지 검사실 P_i에 머문다. 검사실 P_i에서 검사받는 시간은 [e_Pi,i - t_pi +1 e_Pi,i]이다. 각 수검자가 병원을 나서는 예상 검진종료시간은 e_Pn,n이다. <표 1>을 점화식으로 기술하면 다음과 같다.

수검자의 최적 검사경로 P₁P₂…P_n가 결정되면, 해당 검사실 별로 예상 진료 시간에 예약을 한다. 스케줄을 업데이트하는 것은 예약을 하는 것을 말한다. 스케줄 S를 먼저 업데이트하고 이를 이용하여 대기시간 w를 업데이트 한다.

S(p,t)는 시간 t에 검사실 (번호) p의 검사 예약 유무를 의미한다. 프로그램 시작 시, 모든 값을 0으로 초기화한다. S(p,t)가 0이면 예약된 검사가 없음을 말하고, 0이 아니면 시간 t에 어느 수검자가 검사를 받을 것임을 말한다. 각 검사실 P_i(i = 1,2,…,n)에 대해,

여기서 대입하는 값 1을 각 수검자의 ID로 대신할 수 있다.

대기시간 w(p,t)는 수검자가 검사실 p에 시간 t(분)에 도착했을 때 검사를 받기 위해 기다리는 시간으로 정의한다. 다음 <표 2>의 예제를 통해 스케줄 S와 대기시간 w의 관계를 유추할 수 있다. 이 예들은 검사실 p의 평균검사시간 t_p와 스케줄 S가 주어졌을 때 대기시간 w(p,t)를 결정하는 알고리즘에 대한 통찰을 준다.

Table 2.

An example of w(i,t) calculation

이를 통해 최적 경로 P₁P₂…P_n와 예약 스케줄 S가 주어졌을 때 다음 <표 3>과 같이 대기시간 w 업데이트 알고리즘을 도출할 수 있다.

Table 3.

Pseudo code for updating w(i,t)

여기서 count_0s는 배열 S(P_i, •)에서 시점 t부터 시작하여 연속된 0의 개수를 구하는 함수이다.

프로그램 구현시 w와 S는 배열로 선언되는데 모두 0으로 초기화한다. 배열의 크기를 설정하기 위해 접수 마감시간과 병원 종료시간을 설정한다. 다음 <표 4>는 제안한 건강검진 알고리즘의 의사코드를 보여준다.

Table 4.

Pseudo code for the proposed checkup algorithm

검사의 의학적 특성상 또는 병원에서 검사의 효율을 제고하기 위해 지켜져야 하는 규칙이 있는 경우가 있다. 검토 대상이 되는 경로가 이 규칙에 맞는지 여부를 판단하는 것을 유효성 테스트(validity test)라 한다.

예를 들어, 건강검진에서 의학적 특성상 내시경 전 초음파 검사를 받고, 초음파 전 채혈을 하는 경우가 많다. 또한 많은 병원에서 검진의 원활한 진행을 위해 내시경 검사를 마지막에 하는 것을 선호한다. 검사실들이 두 개 층에 나누어 있는 병원의 경우, 수검자들이 1층의 검사를 모두 마치고 2층으로 이동하는 것을 선호하기도 한다. 유효성 테스트는 검사할 항목과 병원의 특성에 따라 달라진다.

우리가 말하는 유효성 테스트는 수검자에게 제시할 경로가 이렇게 필요한 제약 사항들을 모두 지키는 유효한 경로인지 체크하는 것을 말한다. 유효성 테스트는 경로 완전 탐색 시 불필요한 계산을 피하기 위해 경로 소요 시간 식 (1)을 계산하기 전에 수행한다.

유효성 테스트의 구현은 두 가지 방법이 가능하다. 경로(조합)를 모두 생성하여 메모리에 저장해 두고 각각의 경로가 유효한지 체크하여 유효하지 않은 경로를 제거하는 방법과, 경로를 생성하는 함수 안에서 유효하지 않은 조합을 생성 못하게 억제하여 유효한 경로만 반환(return)하도록 하는 방법이 있다. 후자가 메모리 절약, 속도 등의 이점이 있을 수 있다. 하지만, 모든 조합들을 계산하는 것은 기존 함수나 알고리즘을 가져다 써야 하는 경우에 해당하기 때문에, 개발자가 조합들을 계산하는 다양한 방법에 대한 조사와 알고리즘 중간에 개입하여 수정 가능한지 여부의 판단을 잘해야 한다.

지금까지 설명한 알고리즘의 가장 큰 약점은 모든 경로를 조사하기 때문에 시간이 다소 오래 걸릴 수 있다는 점이다. 모든 경로는 수학적으로 조합(permutation)을 의미한다. 예를 들어 15개의 진료실을 방문해야 하는 경우 15!개의 경로를 모두 조사해야 한다. 만약, 검사실을 두 개의 그룹으로 분할해서, 첫 번째 그룹에 속하는 검사를 모두 받은 후에 두 번째 그룹에 속하는 검사를 받게 하는 것이 가능하다면 계산량이 크게 줄어 들 수 있다.

예를 들어, 15개 검사의 가능한 경로의 총 개수는 1,307,674,368,000개이다. 하지만 앞의 8개 검사를 먼저 수행하고 7개 검사를 그 다음에 수행하는 것으로 경로를 제한하는 경우, 처음 8!=40320개의 경로를 조사해서 검사 최소 시간 경로를 구하고, 그 다음 7!=5040개의 경로를 조사해서 검사 최소 시간 경로를 구하여 이어 붙이면 되기 때문에 8!+7!= 45,360으로 고려해야 할 경로의 개수가 현저히 줄어든다. <표 5>는 15개 검사를 두 그룹으로 분할할 때 계산량의 감소를 보여준다. 세 그룹으로 분할할 경우 계산량을 더욱 줄일 수 있다.

Table 5.

Changes in calculation amount due to partitions

검사실 분할은 검사소들의 위치 근접성, 기초 검사를 선행하는 관행 등으로 인해 대부분의 건강검진 병원에서 현실적으로 적용 가능하다. 분할을 적용할 경우, 분할을 유효성 테스트 중 하나로 취급할 수 있다.

각 검사실 별로 하나 이상의 베드(bed)가 있는 경우가 있다. 이 경우 한 검사실에서 하나 이상의 검사가 동시에 진행 가능하다. 이를 구현하기 위해, 우리는 검사실의 각 베드에 스케줄 S와 대기시간 w를 1차원 배열로 할당하고, 위 알고리즘에서 베드 수를 고려한 인덱스 확장이 필요하다.

먼저 검사실은 두 개의 그룹을 이루고 있다고 가정하였다. 절반이 한 그룹이고 나머지가 다른 한 그룹으로서, 그룹 내의 검사실간 이동시간은 1분, 다른 그룹에 속하는 검사실로 이동시간은 2분, 안내데스크에서 모든 검사실로 이동시간은 2분이 걸린다고 가정하였다. 우리는 모든 시간은 숫자로 표시하고 단위는 분(minute)이라 가정한다.

건강 검진을 위한 등록 시작시간은 9시, 이를 숫자로 환산하면 9 × 60 = 540이 된다. 검사등록 마감시간은 15시, 즉 15×60 = 900이다. 구현 시 스케줄과 대기시간 배열의 크기를 정해주기 위해 최대 23시59분까지 검사를 할 수 있다고 가정했다.

검사실의 평균 검사시간은 1 또는 2 또는 3 또는 4로 설정하였고 1이 될 확률은 20%, 2는 40%, 3은 20%, 4는 20%로 설정하였다. 또 검사실의 베드(bed) 수는 1개 또는 2개로 1개일 확률은 50%, 2개일 확률은 50%로 설정하였다.

검사소는 번호로 1부터 시작하여 정수로 표시하였는데 내시경 검사소는 가장 큰 번호로 정하고 내시경 소요시간은 20, 내시경 검사실 내 베드 수는 6개라 가정하였다. 수검자는 안내데스크를 통해 병원에 입장한다고 가정하고 안내데스크의 번호는 0으로 정하였다.

성능에 크게 영향을 미치는 주요 변수에는 검진자수와 검사실수 등 두 가지가 있다. 수검자 수는 100명, 120명, 150명, 180명, 200명 등 5가지 경우, 검사실 수는 10개, 12개, 14개, 16개 등 4가지 경우에 대하여 시뮬레이션을 실시하였다.

오전 9시부터 오후 3시까지 6시간 동안 수검자들이 등록할 수 있기 때문에 6×60 = 360 단위 시간 동안 수검자들이 올 수 있다. 수검자 수는 양적인 의미와 복잡도의 의미를 동시에 가진다. 예를 들어 수검자가 180명이 온다는 이야기는 2분당 한 명꼴로 수검자가 병원에 도착하고 그 만큼 복잡하다는 말이다.

참고로, 경험이 많은 개발자의 말에 의하면 수검자가 수가 하루 평균 300명에 달하는 대형 병원도 있지만, 80명 정도 오는 작은 병원이 많으며, 검사실 수는 12개에서 16개 사이가 실제에 가깝다고 한다.

검사실, 수검자, 유효성 테스트 관련 시뮬레이션 환경 설정을 위해 실무자와 협의하여 다음과 같이 현실성 있게 설정하였다.

검사실별 평균 검사시간은 1분(20%), 2분(40%), 3분(20%), 4분(20%) 중 하나로 랜덤하게 설정하였고, 베드 수도 1개(50%) 또는 2개(50%)중 랜덤하게 선택하였다. 내시경 검사실의 평균검사시간은 20분, 베드 개수는 6개로 고정하였다.

수검자들의 병원 도착시간은 9시와 15시 사이 즉 540과 900사이의 자연수 중 수검자 수만큼 랜덤하게 선택하는 방식으로 설정하였다. 그리고 각 수검자가 받을 검사의 수 n는 검사실수의 40%이상 80%이하로 설정하였다. 예를 들어, 검사실 개수가 16인 경우, 각 수검자는 6.4(=16×0.4)개 이상 12.8(=16×0.8)개 이하 즉 7, 8, 9, 10, 11, 12 중 하나를 랜덤하게 선택하여 선택된 수만큼 검사를 받는다. 검사받을 항목, 즉 방문해야 할 검사실들은 랜덤하게 n개를 선택하였다.

우리는 유효한 경로에 대해 다음과 같이 세 가지 제약 조건을 두었다. 첫 번째는 선행검사 조건으로, 검사 1과 2는 검사 3보다 반드시 앞에 받아야 한다. 두 번째는 분할 조건으로, 검사 1번부터 절반까지가 첫 번째 그룹, 그 다음부터 내시경 검사까지가 두 번째 그룹으로 설정하여 첫 번째 그룹에 속하는 검사가 다 끝나야 두 번째 그룹에 속한 그룹의 검사들을 받을 수 있게 하였다. 세 번째는 내시경 검사를 받는 경우 반드시 마지막에 받아야 한다는 조건을 넣었다.

기존 수동 스케줄링 알고리즘은 한 검사가 종료되는 시점에서, 수검자의 남은 검사들 중 대기시간이 가장 적은 검사를 다음에 받을 검사로 선택한다. 이 규칙은 수검자가 남은 검사 중 다음 식 (5)를 최소로 하는 검사실로 이동하는 탐욕적 알고리즘(greedy algorithm)이라 할 수 있다.

여러 수검자가 차례로 병원에 도착하여 이러한 규칙에 의해 검사를 진행하는 상황에서 각 수검자의 검사 종료시간을 알아내어 제안한 알고리즘과 검사 종료시간을 비교하기 위해 다음 <표 6>과 같이 기존 알고리즘을 구현하였다.

Table 6.

Pseudo code for the pervious greedy algorithm

시뮬레이션에서 각 수검자는 MOVE, WAIT, EXAM 중 하나의 상태(state) 값을 취하도록 하였다. 즉 검사받으러 온 수검자는 어느 검사실로 이동하거나(MOVE), 어느 검사실에서 검사받기 위해 기다리거나(WAIT), 검사를 받는다(EXAM). 각 상태마다 일정한 시간이 필요하다. 이를 위해 timer 변수에 값을 할당하였다. 예를 들어, 검사를 받기 시작하면 상태를 EXAM으로 바꾸고 timer에 그 검사실에 평균 검사시간을 할당한다. 또는 이동을 시작하면 상태를 MOVE로 바꾸고 timer에 평균 이동시간을 할당한다.

MOVE가 종료되고 원하는 검사실에 도착했을 때 그 검사실의 모든 베드가 차있으면 상태를 WAIT로 바꾸고 그 검사실의 대기자 명단(Waiting List)에 추가시키고 WAIT 때는 timer 값을 설정하지 않았다.

Patients_in_Hospital은 현재 병원에 있는 사람들의 리스트(배열)을 말하고 TEND는 검사 등록마감시간이다. 매 루프에서 시간 t는 1분씩 증가하도록 하였다.

update_timer() 함수는 모든 진료실의 모든 베드의 대기시간을 1 감소하고, Patients_in_Hospital에 속한 모든 수검자들의 timer를 1 감소시킨다.

update_room_info() 함수에서는 각 검사실의 대기자 명단에 누군가 있으면 비어있는 그 검사실에 베드가 있는지 조사하고 있으면 대기자 명단의 맨 앞에 있는 수검자를 그 베드에 할당하고 수검자의 상태와 timer를 적절히 설정한다. 모든 베드가 검사 중이면 아무 일도 안 한다.

update_patient_info() 함수에서는 Patients_in_Hospital에 속한 모든 수검자들을 조사하여 timer가 0이 된 경우, 위에서 언급한 데로 상태를 바꾸어 주고 timer를 다시 설정한다. 예를 들어, timer가 0이고 현재 상태가 EXAM인 경우는 검사를 마친 것으로 남은 검사가 없으면 병원을 나가게 하고, 남은 검사가 있으면 위에서 언급한 간단한 규칙에 의해 다음 행선지를 정한다. 그리고 상태를 MOVE로 바꾸고 timer를 해당 이동시간으로 설정한다.

add_new_patient(t) 함수는 현재 시간 t에 도착한 환자를 Patients_in_Hospital에 추가한다.

수혜자는 제안한 알고리즘으로 더 빨리 검사를 마친 수검자로서 Val 값이 양수인 수검자이다. 우리는 전체 수검자중 수혜자들의 비율을 구했다. 이 비율이 높을 수 록 많은 수검자들이 제안한 알고리즘으로 인해 혜택을 보고 검사를 빨리 마칠 수 있었다고 말할 수 있다. 즉 이 비율이 높으면 제안한 알고리즘의 우수성을 입증할 수 있다.

이론적으로 보아 제안한 알고리즘이 기존 알고리즘보다 우월하여 100%가 나와야 하는데 <표 7>에서 보듯 실험 결과는 그렇지 않다. 이는 제안한 알고리즘은 처음에 전체 검사실 방문 스케줄을 결정하는데 반해, 기존 알고리즘은 한 검사를 마친 후 다음 검사 항목을 결정하기 때문이다. 이에 관한 설명은 다음 장에서 예시를 들어 설명하겠다.

Table 7.

Percentage of examinees who completed checkup faster with the proposed algorithm (단위: %)

이는 모든 수검자들의 Val 값 평균을 구하는 것으로, 수검자 한 명당 단축한 검사시간의 평균을 의미한다. 위 수혜자 수와 달리, Val > 0인 경우와 Val ≤ 0인 경우를 모두 포함한다. Val <0인 경우는 단축시간이 음수인 경우로, 제안한 알고리즘이 시간을 더 소비했음을 의미한다.

이를 통해 기존 알고리즘과 비교하여 제안한 알고리즘으로 단축한 평균 시간을 알 수 있다. <표 8>은 수검자 수와 검사실 수 각각에 대해 100회 반복 실험한 결과를 보여 준다.

Table 8.

Average reduction time per an examinee(단위: 분)

괄호 안 숫자는 100회 반복에서 얻어진 단축시간 평균의 표준편차를 말한다. 표에서 볼 수 있듯이 수검자 수가 증가할수록 표준편차가 크게 증가하는 것을 볼 수 있다. 이는 수검자 수가 증가할수록 평균에 대해 신뢰도가 떨어진다는 의미이다. 퍼센티지(%) 값은 기존 알고리즘에 의한 검사 소요시간 평균 대비 단축시간의 비율을 말한다. 예를 들어, 수검자가 100명이고 검사실이 10개인 경우, 수검자 한 명당 14.9분이 단축되었으며, 이 단축시간 14.9분은 기존 검사시간의 32.06%에 해당한다.

그리고 환자 수가 200명일 때는 제안한 알고리즘이 기존 알고리즘보다 좋지 못 한 결과를 얻었다. 4장의 4-2에서 이에 관한 이유를 설명한다.

수혜자는 제안한 알고리즘으로 더 빨리 검사를 마친 수검자로 Val 값이 양수인 경우이다. 우리는 <표 8>의 시뮬레이션 결과를 바탕으로 제안한 알고리즘이 기존 알고리즘 보다 우수한지 통계적으로 검증(statistical test)해 보았다. 이 때 사용한 검증 방식은 짝지어진 표본의 비교(paired t-test)로 H₀ : δ = 0 vs H₁ : δ ≠ 0( 또는 H₁ : δ < 0)으로 p-value는 0.01로 설정하였다.

<표 9>는 통계적 검증의 결과를 보여 준다. 표에서 Sig.는 통계적으로 유의미한 것으로, 간단히 말하면, 제안한 알고리즘이 기존 알고리즘보다 더 좋다는 것을 의미한다. Sig.(-)는 기존 알고리즘이 통계적으로 더 좋다는 것을, Insig.는 두 알고리즘의 성능이 통계적으로 우열을 가리기 어렵다는 것을 의미한다.

Table 9.

Average reduction time per an examinee(단위: 분)

<표 9>의 시뮬레이션 결과를 통해, 수검자 수가 180이하 인 경우 제안한 알고리즘이 더 우수하며, 수검자수가 200인 경우 둘 간의 차이가 없거나 제안한 알고리즘보다 기존 알고리즘이 더 우수한 것을 알 수 있다. 간단히 말해, 우리 알고리즘은 수검자 수가 180이하인 경우, 즉 2분에 한 명이하의 수검자가 내방하는 복잡도를 가지는 경우에 유효하다고 말할 수 있다.