A Case Study on the Air Force Base-level Crew Scheduling

미국 공군의 군수준비대(Logistics Readiness Squadron, LRS)는 자재 관리, 분배 및 비상 작전을 담당하는 부대이다. LRS의 기지 내 차량 운송계획 담당부서는 요구되는 운송 시간, 운송의 우선순위, 비정기적 다발성 운송 임무 등 다양한 제약을 고려하여 고객의 요구에 맞는 운송 일정을 일일 단위로 작성해야 하는 임무가 있다. LRS는 자동화된 스케쥴링 도구의 부재로 인하여 담당자는 수작업으로 운송계획을 작성하고 있으며, 운송 담당 승무원 부족 등 문제점을 안고 있다. 본 연구의 목적은 LRS 내 제약사항들을 고려하여 인적자원 부족 문제를 효율적으로 해결하고, 운송 요구 사항을 충족하는 스케쥴 생성툴을 개발하는 것이다. 본 연구에서는 단일 창고(depot)를 갖춘 기지 수준의 운송 시스템에서 승무원 일정을 효율적으로 계획할 수 있는 자동화된 스케줄링툴을 개발하였다. Microsoft Excel® Solver를 기반으로 일일 비행대 스케줄러(Daily Squadron Scheduler, DSS) 프로그램을 제작하였고, 셋 커버링 문제 접근법과 선형 프로그래밍 프라이싱 알고리즘을 활용하여 구현하였다. 하위문제(sub-problem)에서 도출된 절감비용(reduced cost) 과 잠재가치(shadow price) 개념을 활용하여 유효한 정수해를 생성하였다.