근무생성기.cell

진행 기간: 2020.08~2021.10
마지막 수정: 2022-12-04 15:08:53 +0900

Hancell VBA Machine Learning Genetic Algorithm

공정한 근무 할당 및 생성을 위한 한셀 파일

들어가기에 앞서

한셀이 무엇인지 궁금할 수 있다. 한셀은 한글과컴퓨터에서 만든 오피스 프로그램인 한컴오피스에 포함된 프로그램 중 하나이다. MS Office와 비교하면 비슷한 역할을 하는 프로그램은 아래와 같다.

MS Office	한컴오피스
Word	한글, 한워드
Excel	한셀
Powerpoint	한쇼

이 중에서 MS Office의 Excel과 비슷한 역할을 하는 것이 한셀이다. 그 중에서도 한컴오피스 2018 버전에 있는 한셀 2018을 사용한다. 하지만 한셀은 엑셀에 비해 잔버그가 많고 Form을 사용할 수 없다. 여기에 VBA 객체는 엑셀에서 가져온 것으로 보이는 것이 많다.¹ 그리고 군대에서 사용하는 버전은 [국방부] 한셀 2018인데, 이 버전은 일부 이벤트를 빈 코드나 의미없는 코드로 덮어씌워 이벤트의 실행 자체를 막아놓았다. 사실상 제약이 매우 심한 버전이라고 볼 수 있다.

계기

훈련소 수료 후 부대에 전입을 온 뒤 얼마 있지 않아 같은 생활관 선임 A가 갑자기 다른 분대 선임을 한 명 소개시켜줬다. 그 선임은 수송부 수리부속계원으로 일하고 있었는데, 본래의 업무에 더해 중대의 근무를 편성하는 일도 하고 있었다. 같은 생활관 선임 B도 이 일을 같이 하고 있었는데 전역할 때가 되어 부사수를 찾고 있었다. 마침 군대에서 코딩도 못하는거 이거라도 하면서 감을 유지해야겠다는 생각에 이 일을 하기로 했다.(그 이전에 이런 것처럼 무언가 관리하는 일을 하는 것을 좋아하기도 했다)

Season 1 (2020.08~2020.11)

같은 생활관의 선임 B와 이 시점에서 같이 일하는 선임이 내가 부대에 전입오기 전 사용하고 있던 버전이다. 이 버전 유지보수에는 참여했지만 제작에는 참여하지 않아 프로그램이 돌아가는 방법을 간단하게만 설명한다.

이 때 사용하던 파일은 군대 컴퓨터 내에 있고, 이 파일을 외부로 빼오는 과정이 상당히 복잡하고 보안 상의 이유도 있어 원본을 구할 수 없다.

루틴

이 파일을 사용하는 정해진 방법은 없지만 보통 아래와 같은 순서로 사용한다.

이월 전 루틴: 매월 달이 넘어가기 전 월별로 처리해야 하는 것을 진행하는 루틴이다.
1. 총 인원에 변동이 생기는 경우 반영한다.
2. 다음 달에 대하여 인원 별 열외 현황을 조사한다.(당직부사관, 상황병, 당직대기, 의무대기 등)
3. 열외 현황에 따라 근무 횟수를 조정한다.(조정 매크로를 실행한다)
근무 생성 루틴: 근무를 생성할 때마다 진행하는 루틴이다.
1. 신병이 전입오는 경우 인원에 추가한다.
2. 근무를 생성할 기간을 설정한다.
3. 이 기간에 열외를 입력해야 하는 경우 파일 자체적으로 가지고 있는 열외 입력 매크로를 사용하거나 수동으로 입력한다.
4. 새로 추가된 열외에 맞게 인원 별로 공정도를 조정한다.
5. 근무를 생성하려는 기간에 포함된 일자 별로 공정도 상 근무가 들어가야 하는 인원을 뽑는다.
  - 만약 전날 근무가 들어있는 인원은 제외하고 새로운 인원을 다시 뽑는다.(다시 뽑지 않고 그대로 투입시키는 옵션 존재)
6. 특정 근무에만 들어가는 인원의 경우 위치를 조정한다.

열외 사항

전체 열외: 열외 사항 중 근무에 아예 포함되지 않는 인원들이 있다. 열외 사유는 당직부사관, 상황병, 의무대기 운전병, 1호차 운전병, 취사병, 동절기 기간 보일러병 등이 있다.
부분 열외: 열외 사항 중 일부 기간에 근무로부터 열외되는 인원들이 있다. 열외 사유는 보통 물자취급장비운전병, 당직대기 운전병, 출타 등이 있다.

근무 편성

근무 편성 직전 인원 별로 서야 하는 근무의 횟수가 정해져있다. 이는 후술할 공정도 값을 적용시켜

Season 1 파일의 백엔드는 선임 B가 개발하고 전역을 했는데, 코드를 분석해본 결과 특수한 경우에 대하여 무한루프에 빠질 수도 있는 방법을 사용하고 있었다.² 이 방법 대신 다른 방법을 사용해야겠다는 생각도 Season 2 제작 결심에 영향을 미쳤다.

근무 횟수 지정(공정도)

Season 1의 파일은 첫 시트에 일부 변수를 조정할 수 있는 셀이 있다. 예를 들어 신병이 전입을 오는 경우 언제부터 근무를 투입시킬지, 곧 전역하는 인원은 전역하기 며칠 전부터 근무를 제외시킬지, 며칠 이상 근무에서 열외되는 경우 근무 수 조정이 들어가는지, 얼만큼 조정하는지 등이 있다. 이 중 뒤의 2개의 변수를 사용하여 공정도를 조정한다. 일반적인 상황에서는 7일 연속으로 근무 열외 시 근무 2개를 선 것으로 인정해준다. 하지만 근무를 들어갈 수 있는 인원의 수가 너무 적어지거나 너무 많아지면 이 수를 적당히 조정한다. 7일에 3개로 조정한 적도 있고, 8일에 2개로 조정한 적도 있다.

이렇게 조정된 근무 수를 따져서 다른 인원에 비해 근무 수가 과하게 많이 들어간 인원이 있으면 다음 달 근무를 생성할 때 1회 덜 들어가게 조정한다.

평가

어쩔 수 없이 수동으로 기입해야 하는 내용을 제외하면 대부분 자동화되어있었던 것이 매우 편리했다. 마침 인사계원과 같은 PC를 사용했는데, 인사계원이 사용하는 휴가 종합 파일에서 휴가 정보를 가져오는 것도 버튼 한 번만 클릭하면 자동으로 정보를 수집했다. 그리고 내가 부사수로 들어간 이후 근무 열외 조건이 바뀌거나 새로운 열외가 생기는 경우도 있고, 기능적인 측면에서 추가하고 싶은 내용이 있어서 추가하기도 했다. 한셀 파일인 것 치고는 조금 허술한 프로그램 수준으로 보일 정도로 완성도가 상당했던 파일이었다. 하지만 중대가 불침번만 서다가 갑자기 초소 근무가 생겨서 이를 커버하기 위해서는 새로운 파일이 필요했다. 근무 내용 및 환경 변화에 유동적으로 대처할 수 있고, 수학적인 분석을 통해 조금 더 공정한 근무 횟수를 만들 수 있는 파일이 필요했던 것이다.

Season 2 (2020.12~2021.10)

새로운 종류의 근무가 생겨 여러 종류의 근무를 한 번에 처리하기 위해 만든 새로운 버전이다. 알고리즘에도 변화를 주어 더욱 공정한 근무를 짰다(고 주장한다).

Season 1은 근무 종류가 불침번 하나였던 것에 비해 초소 근무가 하나 생겼는데, 이로 인해 많은 것들을 새로 구상하게 되었다. 그리고 구상에 있어서 연세대학교 석사학위 논문으로 사용된 [유전알고리즘을 이용한 간호사 업무 평준화 스케줄에 대한 연구 : 군병원 간호장교를 중심으로 / 저자: 노우협]라는 논문을 참고했다.

근무 종류 별 열외 파악(열외파악기.cell)

Season 1 때에는 당직부사관, 상황병, 당직대기 운전병 등 필수 인원은 모두 열외시키고 출타 등과 같은 부분적인 열외는 적당히 반영해서 해당 일에 근무가 들어가지 않도록 지정했는데, 근무 종류 별로 한 열외 사유로 인하여 열외되는 것이 달라졌기 때문에 이를 보다 효율적으로 종합할 수 있는 방법이 필요했다. 이는 프론트엔드 개발에 흥미를 가졌던 선임이 구상 및 개발하는 것으로 했다.

공정한 근무 횟수 / 공정도

근무의 종류가 하나 추가된 것 때문에 기존 Season 1보다 합리적인 근무 횟수를 지정하는 방법이 필요했다. Season 1은 정수 단위로 제어했고, 연속 n일에 m개 근무 조정이라 n-1일 열외인 인원은 아예 근무 조정을 받지 못하는 등 형평성의 문제에 있어서 조금 문제가 있었다. 이러한 현상에 대한 답안으로 설 수 있는 날의 비율의 거듭제곱꼴을 사용하는 것이 적당하다고 생각했다. 전반적으로 한 달 중 절반을 열외하는 사람은 후술할 일명 “퐁퐁” 문제에 있어서 비교적 자유로운 상황일 것이다. 열외 기간 앞뒤 날에 근무가 들어간다면 퐁퐁이 아니라는 조건으로 약간 근무를 더 설 수 있다고 생각했다. 그리고 적절한 상수를 구해서 아래와 같은 기대 근무수를 만들었다. 한 달 중 열외가 이 정도이면 전체 기간 근무를 서는 인원에 비해 어느 정도의 근무를 들어가면 된다는 의미이다.

\[f=\left(\frac{n_a}{n_m}\right)^{c}\]

여기서 f는 기대 근무 비율, n_a는 한 달 중 근무를 설 수 있는 날의 수, n_m는 한 달에 속한 날 수, c는 비율에 제곱하는 상수이다. 이 수는 구상 당시 0.8로 정의했다. 하지만 제곱 연산에 의한 근무 증가 효과가 너무 심하다고 판단하여 나중에 2달에 걸쳐 0.85, 0.9로 값을 바꿨다. 위 식에 따라 구한 한 달에 설 수 있는 날에 대한 기대 근무 비율 값은 아래와 같다.

한 달에 설 수 있는 날에 대한 기대 근무 비율(한 달 30일 기준)

근무 가능일	근무 가능 비율	기대 근무 비율(c=0.8)	기대 근무 비율(c=0.85)	기대 근무 비율(c=0.9)
0	0	0	0	0
3	0.1	0.158	0.141	0.126
6	0.2	0.276	0.255	0.235
9	0.3	0.382	0.359	0.338
12	0.4	0.480	0.459	0.438
15	0.5	0.574	0.555	0.536
18	0.6	0.665	0.648	0.631
21	0.7	0.752	0.738	0.725
24	0.8	0.837	0.827	0.818
27	0.9	0.919	0.914	0.910
30	1	1	1	1

이 공정도 값을 사용하여 한 달동안 특정 인원이 서야 할 근무의 값을 예측할 수 있다. 총 근무의 개수를 W라고 하면 아래와 같은 식을 통해 근무의 수를 정할 수 있다.

\[w_k=\frac{f_k}{\sum_i{f_i}}W\\ \begin{aligned} \therefore\sum_j{w_j}&=\frac{W}{\sum_i{f_i}}\sum_j{f_j}\\ &=W\frac{\sum_i{f_i}}{\sum_j{f_j}}\\ &=W \end{aligned}\]

즉, 모든 인원의 기대 근무 수를 더하면 전체 근무 수가 나온다. 하지만 여기서 근무 수라는 개념은 정수인데 기대 근무 수는 소수점이 포함된 실수이다. 즉, 기대한 값과 실제 들어간 근무 수에는 차이가 있을 수 밖에 없다. 이 차이를 공정도라고 정의한다.³ 기대 근무 수의 합이 전체 근무 수인만큼 모든 인원의 공정도를 합하면 0이 된다. 그렇기 때문에 공정도의 표준편차(또는 분산)를 최소로 하는 방향으로 근무를 짜면 더욱 공정한 근무를 생성한 것이라고 말할 수 있을 것이다.

근무 생성 / 유전 알고리즘

Season 1 때는 공정도 값을 기반으로 남은 근무 수가 많은 사람부터 랜덤으로 배정하는 방식을 사용했다. 이 방법은 나름대로 상황에 맞게 잘 작동하는 휴리스틱 알고리즘이었다. 큰 변화만 없으면 오류없이 잘 작동했다. 하지만 Season 2를 만드는 김에 조금 더 고르게 퍼져있는 자연스러운 근무를 짜고 싶었고, 내친김에 머신러닝 기법 중 하나를 사용해보고 싶었다. 그래서 생각해낸 것이 유전 알고리즘이다. 고등학교 3학년 때 친구가 유전 알고리즘으로 게임 AI를 만드는 졸업논문을 작성할 때 프로그램 제작을 도와준 적이 있기 때문에 근무생성기에 유전 알고리즘을 사용하는 것이 다른 머신러닝 기법에 비해 익숙했고 더 빠르게 제작을 할 수 있겠다고 생각했다.

유전 알고리즘에 대한 간단한 설명은 아래와 같다.

유전자 생성
교차
돌연변이
적합도 계산
적합도 기반 유전자 선택
적당한 유전자가 존재하면 작동 종료, 아니면 2번으로 돌아감

유전자의 형태

근무생성기에서 사용하는 유전자는 논문과는 조금 다른 의미를 가진다. 논문에서는 유전자를 인원 별로 근무 투입 여부를 표현한 bit-string 형태의 풀에 속한 각 bit를 유전자로 칭했지만, 여기서는 생성하려는 기간 전체의 근무표 전체를 하나의 유전자로 본다. 즉, 누가 어떤 근무를 들어가는지를 모두 포함한 int-matrix 형태의 데이터 자체가 하나의 유전자다. 대략적인 형태는 아래와 같다. 9명이 하루에 3개 있는 근무를 매일 서는 상황을 가정했다.

유전자 예시

적합도

유전자 별로 적합도라는 변수가 존재한다. 이 값은 유전자가 문제의 해에 얼마나 근접했는지를 의미하는 척도로 유전 알고리즘이 얼마나 진행되었는지 판단할 때 사용할 수 있고 유전자 선택 과정에서 어떤 유전자를 다음 세대로 넘길지 정할 때도 사용할 수 있다. 유전자 선택에서 이 값을 사용한다면 적합도 순서대로 나열한 후 상위 유전자를 선택하는 방법도 있고 완전 랜덤으로 선택하는 방법도 있다. 그 이외에도 다양한 방법이 존재한다.

근무생성기에서 사용할 적합도는 인원 별로 열외인 날에 근무가 들어가는지, 퐁퐁(근무를 n일 연속으로 들어가는 것)이 있는지에 대한 값을 가진다. 열외인 날에 근무가 들어가는 것은 안되므로 큰 값, 퐁퐁은 들어가도 되나 지양해야 하는 것이므로 작은 값을 할당한다. 열외인 날 근무 투입 시마다, 퐁퐁이 생길 때마다 적합도가 증가하게 설정을 해놓았기 때문에 일반적인 유전 알고리즘과는 다르게 해에 가까울수록 적합도는 낮은 값을 갖는다. 따라서 이 적합도가 낮을수록 합리적인 근무가 짜였다고 볼 수 있다. 이 적합도를 기반으로 유전자 선택 과정과 유전 알고리즘 중단 여부를 결정한다.

유전 알고리즘 변형

유전자의 형태가 논문처럼 유전 알고리즘을 그대로 적용할 수 있는 형태는 아니었기 때문에 일부 수정이 필요했다. 위 유전자의 형태에 대하여 가장 구상하기 까다로운 교차 과정을 제외하기로 했다. 교차를 진행했을 때 앞에서 지정해놓은 인원 별 근무 횟수가 바뀔 수 있기 때문이다. 그래서 근무생성기에서 사용하는 유전 알고리즘은 아래와 같이 된다.

유전자 생성
돌연변이
적합도 계산
적합도 기반 유전자 선택
적당한 유전자가 존재하면 작동 종료, 아니면 2번으로 돌아감

근무 관리 및 공정도 판별

근무는 보통 한 번에 7~10일씩 생성한다. 그런데 공정도는 한 달을 기준으로 부여하게 되어있다. 그렇기 때문에 한 달의 일부 근무만 짜여진 상태에서의 공정도가 존재한다. 이는 근무 별 시트와 종합 시트를 통하여 인원 별로 공정도를 저장함으로써 유지한다. 이 값은 이후 근무를 생성할 때 사용하며, 현재의 공정도 분포에 대해서 현재 공정도와 새로운 공정도의 합의 분산이 작아지는 방향으로 근무 횟수를 설정한다.

또한 공정도는 이월된다. 매 달 전역하는 인원의 공정도를 제외한 다음 평균을 0으로 맞춘 후 다음 달로 공정도 값을 넘긴다. 이는 어느 한 달의 공정도가 잘못되도 그에 대한 보상을 이후에 지급할 수 있게 하기 위함이다. 이월된 공정도는 해당 달의 공정도와 동일하게 작용한다.

이를 포함한 전체적인 과정을 표현하면 아래와 같다.

월 별 루틴
1. 열외파악기.cell을 사용하여 월 별 열외 변동사항 최신화(당직병, 상황병, 보직에 따른 열외사항 등)
2. 근무생성기.cell로 열외 정보 복사
3. 이전 달 공정도 이월
  - 전역(전 휴가) 인원 제외 후 평균 산정 및 평균이 0이 되게 변환 후 이동
근무 생성 루틴

Mso는 Microsoft Office, Xl은 발음이 Excel이다. 한셀의 VBA 객체 중 수십 개가 Mso*와 Xl* 형태를 가진다. Hnc*로 시작하는 객체는 거의 못봤고 _Global 객체 안에 Hnc* 형태인 상수를 몇 개 본 것 같다. 이 정도면 엑셀을 그대로 포크를 떠서 사용한 것을 의심할 수 밖에 없다. ↩
while true문이 2개 중첩된 부분도 있었고 goto도 정말 많이 사용했다. 선임 B는 이 알고리즘이 잘 작동할 것이라고 확신을 했다고 추측해볼 수 있다. ↩
Season 1의 공정도와는 조금 다른 개념이다. Season 1에서는 n일 연속 근무 열외로 인하여 조정된 근무의 수를 공정도라고 했는데, Season 2에서는 기대 근무 수와의 오차를 공정도라고 정의했다. ↩