FLOW Engine과 Diagnostic Engine
안녕하세요. NurseFLOW 디렉터입니다.
" 현직 간호사가 직접 만든 AI-based Nurse Scheduling Solution "
3교대 간호사 근무표. 저는 완전한 자유를 얻었습니다.
여러분도 그렇게 되기를 희망합니다.
3교대 간호사 근무표 AI 자동생성 프로그램
NurseFLOW.
이번에는 NurseFLOW의 핵심 엔진 3종 중 2종인 FLOW Engine과 Diagnostic Engine에 대해 말씀드리겠습니다.
간호사 근무표는 왜 어려운 문제일까요?
간호사 근무표는 [ 간호사 X 날짜 ]의 2차원 표로 표현되는, 오랫동안 쉽게 풀리지 않은 유명한 최적화(Optimization) 문제입니다.
(구글의 CP-SAT 공식문서에서는 Optimization의 대표예시로 간호사 근무표를 들었습니다.)
간호사 20명의 30일치 근무표를 예시로 들어봅시다. 600개(20X30)의 칸에 각각 D/E/N/Off 네 가지가 들어갈 수 있으니
단순히 따지면 4의 600제곱이라는 천문학적인 경우의 수가 나옵니다.
근무표를 짤 때 맨 앞칸부터 하나씩 채워넣으며 일일이 비교하는 방식을
브루트포스 (Brute Force) 라고 합니다.
물론 근무에는 규칙성이 있어 4의 600제곱인 모든 경우의 수를 다 볼 필요는 없지만,
이 방식만으로는 사실상 셀 수 없이 많은 경우를 뒤져야 최적의 근무표에 도달합니다.
엑셀로 손수 근무표를 짜는것도 본질적으로는 이 '브루트 포스'에 가깝습니다.
제약조건 프로그래밍 (Constraint Programming)
NurseFLOW는 Google의 OR-Tools CP-SAT Solver를 응용한 제약조건 프로그래밍 솔루션입니다.
복잡한 제약조건을 수식으로 표현해 간호사 근무 최적화 문제를 풀어냅니다.
그 메커니즘은 크게 두 단계로 나눌 수 있습니다.
1단계 / 성립 여부 확인 (Feasibility)
FLOW Engine의 첫 번째 목적은
'이 근무표가 성립할 수 있는가(Feasibility)?'를 확인하는 것입니다.
제약조건 중에는 반드시 지켜야 하는 규칙(경성제약)이 있습니다.
이 규칙을 만족할 수 없다면 그 근무표는 브루트포스로 탐색할 필요조차 없습니다.
게다가 30개가 넘는 제약조건들은 서로 보완적이면서 동시에 충돌하기도 하고,
같은 조건이라도, 간호사/부서/조직의 속성에 따라 지킬 수 없게 되기도 합니다.
간단한 예시를 보겠습니다.
어떤 3교대 병동에서 D·E·N 각 근무에 3명씩 필요하다면, 하루 9명 → 한 달이면 270개의 근무가 필요합니다.
그런데 간호사가 12명이고 30일 중 휴일 10일을 반드시 보장해야 한다면, 실제 가능한 근무일은 12명 × 20일 = 240일뿐입니다.
수요(270)가 공급(240)보다 30만큼 많으므로, 이 근무표는 애초에 성립할 수 없습니다.
이러한 사전검증으로 성립가능여부부터 먼저 판별하면, 처음부터 끝까지 브루트포스로 뒤질 필요가 없어집니다.
또한, 흔히 '조건이 많아지면 계산이 느려진다' 라고 생각하기 쉽지만
CP-SAT Solver에서는 오히려 반대일 수 있습니다.
제약이 늘어나면 늘어날 수록, 가능/불가능의 경우의 수가 더 좁혀지기 때문입니다.
바로 이 점이 간호사 근무표 문제에 제약조건 프로그래밍이 꼭 필요한 이유입니다.
2단계 / 최적해 찾기 (Optimization)
성립이 가능하다면 (Feasible), 그 다음 목표는
'가장 좋은 근무표'를 찾는 것입니다.
이 최적화를 담당하는 것이 NurseFLOW의 CP-SAT 응용 알고리즘, FLOW Engine 입니다.
'가장 좋은 근무표'의 기준은 두 가지입니다.
1. 모든 경성제약(Hard Constraints, 반드시 지켜야 하는 규칙)을 만족한다.
2. 연성제약의 페널티 총합이 최소이다. (이상적으로는 0)
여기서 '연성제약'이란, '반드시는 아니어도 웬만하면 지켜야 하는 조건들로,
기피근무/기피근무 패턴 등이 여기에 속합니다.
주의할 점은, 패널티가 0인 '완벽한(Optimal)' 근무표는 있을 수도, 없을 수도 있다는 것입니다.
그래서 FLOW Engine의 목표는 무조건적인 패널티 '0'이 아니라,
달성 가능한 범위에서 '페널티 총합이 가장 낮은 근무표'를 찾는 것입니다.
두 근무표의 페널티 총합을 비교하는 일은 어렵지 않으므로,
더 낮은 쪽을 반복적으로 찾아 완벽(Optimal)에 가장 가까우면서
모든 필수규칙을 만족하는 (Feasible) 해에 도달하도록 합니다.
해가 없을때 / Diagnostic Engine
오늘 이 글을 작성하는 이유가 바로 여기있습니다.
NurseFLOW는 해가 없다고 바로 못박아버리지 않습니다.
근무표가 만들어지지 않았나요? 끝이 아닙니다.
오히려 작성에 실패했을 때, 그 원인을 어떻게 진단하느냐가 더 중요합니다.
근무표가 성립 불가능(Infeasible)으로 판정되면,
NurseFLOW의 Diagnositc Engine은 어떤 제약조건이 서로 충돌하는지를 분석합니다.
진단은 NurseFLOW의 특수알고리즘을 통해 다차원형태로 분석합니다.
일반적인 부서 규모(간호사 20~40명)에서 FLOW Engine의 근무표 성립 여부 확인은 250~500ms 정도가 걸리고,
Diagnostic Engine이 모든 진단을 5~15초 이내에 마칩니다.
그 결과 사용자는 어떤 제약조건과 요청을 풀어야 근무표가 만들어지는지를
구체적으로 제안받게 됩니다.
Diagnostic solver는 다른 프로그램에서는 볼 수 없습니다.
오직 NurseFLOW에서만 확인하실 수 있습니다.
NurseFLOW의 놀라운 기능을 경험해보고싶다면 참여해보세요.
사용문의
skyleester@nurseflow.icu