[Paper] 외래 환자 예약 스케줄링 최적화: Genetic Algorithm 접근법

Source: arXiv - 2602.21995v1

개요

다수의 클리닉에 걸친 외래 진료 예약을 조정하는 일은 악명 높은 복잡한 문제입니다—임상 안전 규정, 환자 이동, 제한된 자원이 종종 충돌하여 예약 누락 및 긴 대기 시간을 초래합니다. Rodrigues와 Rego는 유전 알고리즘(GA)을 사용해 이 문제에 직접적으로 접근하여 자동으로 실행 가능하고 환자 친화적인 일정을 생성함으로써, 진화적 접근법이 전통적인 선착순(FCFS) 방식보다 우수할 수 있음을 보여줍니다.

주요 기여

• GA‑based scheduling framework 복잡한 절차 간 비호환 제약(예: “절차 A는 같은 날 절차 B 뒤에 올 수 없음”)을 준수합니다.
• Two GA variants (Pre‑Ordered와 Unordered) 를 결정론적(FCFS) 및 확률론적(Random Choice) 기준선과 비교 평가했습니다.
• 100 % constraint‑fulfillment rate 네 개 보건센터에 걸친 50개의 의료 행위 합성 데이터셋에서 100 % 제약 충족률을 달성했습니다.
• Significant reductions 환자 중심 지표에서 큰 감소를 보였으며, 대부분의 실행에서 유휴 시간 비율(ITR) < 0.4 및 센터 간 이동 횟수가 감소했습니다.
• Statistical validation (p < 0.001) 로 GA 솔루션이 우연이 아님을 확인했습니다.
• Insight into GA dynamics Ordered 변형이 더 빠르게 좋은 솔루션을 찾지만, 두 변형 모두 100세대까지 유사한 최적값에 수렴합니다.

방법론

1. Problem formulation – 저자들은 예약‑스케줄링 작업을 각 “gene”(유전자)이 특정 의료 행위와 할당된 시간 슬롯 및 위치를 인코딩하는 조합 최적화 문제로 모델링한다. 하드 제약조건(임상적 부적합성, 자원 용량)은 페널티 항으로 인코딩된다.
2. Genetic representation –
   • Pre‑Ordered GA: 염색체는 이미 휴리스틱(예: earliest‑deadline first)으로 정렬된 행위들의 순서이다.
   • Unordered GA: 염색체는 무작위 순열이며, GA가 순서를 스스로 발견하도록 한다.
3. Evolutionary operators – 표준 교차 및 변이 연산자를 가능한 한 타당성을 유지하도록 조정한다; 타당하지 않은 자손은 간단한 탐욕적 후‑처리 단계로 복구한다.
4. Fitness function – (a) 위반된 제약마다 큰 페널티를 부여하여 알고리즘이 타당성을 우선시하도록 하고, (b) 환자 중심 목표(유휴 시간 최소화, 이동 거리 최소화, 전체 makespan 최소화)의 가중합을 결합한다.
5. Experimental setup – 50개의 행위, 4개의 클리닉, 현실적인 부적합 규칙을 포함한 합성 벤치마크. 각 GA는 인구 200명으로 100세대 실행되며, 통계적 견고성을 위해 30번 반복한다. 기준선(FCFS, Random)은 동일한 데이터에서 직접 비교를 위해 실행한다.

결과 및 발견

• 두 GA 변형 모두 제약 위반을 모두 제거합니다. 이는 대부분의 경우 FCFS가 달성하지 못하는 것입니다.
• 환자 중심 지표가 크게 개선됩니다: ITR이 약 40 % 감소하고 여행 부담이 절반으로 줄어듭니다.
• Ordered GA는 거의 최적에 가까운 해를 더 빠르게 찾지만, 약 100세대 후에 Unordered GA가 따라잡아 두 설계 모두 탐색 공간을 잘 탐색함을 확인합니다.
• 통계적 검정(쌍체 t‑검정) 결과 개선이 **매우 유의미함(p < 0.001)**을 확인했습니다.

실용적 함의

• 자동 스케줄링 엔진은 다중 클리닉 네트워크에서 수동적이고 오류가 발생하기 쉬운 스프레드시트를 대체할 수 있어, 행정 직원이 더 높은 부가가치 업무에 집중할 수 있게 합니다.
• 환자 대기 시간 및 이동 시간 감소는 직접적으로 만족도 점수 상승과 노쇼율 감소로 이어지며, 이는 외래 서비스의 핵심 성과 지표입니다.
• GA 프레임워크는 모듈식이며, 새로운 제약 조건(예: 장비 살균 시간, 진료자 선호도)을 전체 시스템을 재설계하지 않고도 페널티 항으로 추가할 수 있습니다.
• 확장성: 50개의 작업에 대해 테스트했지만, 알고리즘의 선형 시간 적합도 평가와 병렬화 가능한 개체군 동역학 덕분에 수백 개의 일일 예약이 있는 더 큰 실제 일정에도 적합합니다.
• 통합 경로 – 이 접근 방식은 REST API를 제공하는 마이크로서비스로 래핑될 수 있어, 기존 전자 건강 기록(EHR) 또는 병원 정보 시스템(HIS) 플랫폼이 필요에 따라 최적화된 일정을 요청할 수 있습니다.

제한 사항 및 향후 연구

• Synthetic data: 연구에서는 생성된 데이터셋을 사용했으며, 실제 환경에서의 검증을 위해 실시간 예약 로그에 대한 검증이 필요합니다. 이는 잡음이 많고 불완전한 정보에 대한 견고성을 평가하기 위함입니다.
• Static constraints: 현재 모델은 고정된 비호환 규칙 집합을 가정합니다; 동적 제약(예: 갑작스러운 장비 고장)은 온라인 재최적화를 필요로 합니다.
• Computational budget: 수렴에 약 100세대가 소요됩니다; 매우 큰 일정의 경우 실행 시간이 병목이 될 수 있으므로, 향후 연구에서는 하이브리드 메타휴리스틱이나 GPU 가속 평가를 탐색할 수 있습니다.
• User acceptance: 논문에서는 임상의가 생성된 일정과 어떻게 상호작용하거나 이를 무시할지에 대해 다루지 않았으며, 이는 채택에 중요한 요소입니다.

핵심: 잘 조정된 유전 알고리즘이 완전히 규정을 준수하고 환자 친화적인 외래 일정을 생성할 수 있음을 보여줌으로써, Rodrigues와 Rego는 의료 제공자가 전통적으로 수동적인 프로세스를 현대화할 수 있는 길을 열었습니다—낭비를 줄이고, 안전성을 향상시키며, 환자와 직원 모두에게 더 원활한 경험을 제공합니다.

저자

• Ana Rodrigues
• Rui Rego

논문 정보

• arXiv ID: 2602.21995v1
• 분류: cs.NE, cs.LG
• 출판일: 2026년 2월 25일
• PDF: PDF 다운로드