This dissertation focuses on operations planning problems arising in the army aviation units of Korea. There are two types of aviation units in the army, assault units and mobility units. An assault unit performs missions of attacking enemy’s aircrafts, armors and combat forces and protecting friendly units including mobility aviation units, while a mobility aviation unit conducts transportation missions such as maneuvering infantry forces to decisive areas against enemy and/or moving ammunitions and equipments to a place where they are needed. In this study, we focus on scheduling problems in mobility aviation units. As can be seen from the recent wars, mobility aviation units have played important roles to support ground combat forces by supplying war materials. However, since there are a limited number of aviation units and aircrafts in each unit, it is required to develop methodologies to complete all given missions as early as possible within the limited resources.
First, we consider a problem which is to assign the flight missions to the aircrafts and schedule these assigned missions on each aircraft with the objective of minimizing makespan, i.e., the time all missions have been completed. Sequence-dependent setup times are required between the missions, and multiple aircrafts may be needed for a mission if work required for the mission exceeds the capacity of an aircraft, but the aircrafts assigned to the same mission should start the mission simultaneously. We develop two methods to convert a sequence of (partial) missions to a (partial) schedule for the problem. Based on the converting methods, we develop several heuristic algorithms for the problem which are composed of two-step procedures: obtaining an initial sequence (solution) of missions in the first step and improving the solution in the second step.
Secondly, we consider a situation in which the flight missions are already allocated to each pilot (aircraft) based on pilots’ flight skill, experiences and familiarity of mission areas. A mission can be performed by multiple aircrafts when the mission exceeds the capacity of an aircraft and the aircrafts assigned to the same mission have to perform the mission simultaneously. The problem is to schedule the assigned missions on each aircraft to minimize makepan. We propose a branch and bound algorithm including dominance properties, lower bounds and heuristic algorithms for the problem which can be used as methods to obtain an initial upper bound for the B&B algorithm as well as can be used to solve practical size of problems in mobility units.
We have performed a series of experimental tests on problem instances which reflect a real situation in a way. Results showed that the heuristic algorithms for the first topic give good or near-optimal solutions in a short time and the branch and bound algorithm for the second topic could solve problem instances up to medium-size in reasonable amount of computation time and showed better performance than the benchmarks (CPLEX). Also, the algorithms suggested in this dissertation can be used for scheduling problems in mobility units as well as for scheduling problems in other applications with slight modifications if it is needed.
본 논문에서는 육군 항공부대에서 발생되는 스케줄링 문제를 다루고 있다. 특히, 최근 전쟁양상을 살펴보면, 지상 기동부대의 기동속도가 과거 전쟁에 비하여 매우 빨라졌으며, 이에 따른 효과적인 보급선 유지를 통한 지상 전투부대의 전투지속능력을 유지시키는 것이 매우 중요한 문제가 되었다. 또한, 한국의 지형적 특성을 고려하였을 때, 전쟁 초기 원활한 지상 보급로를 유지하는 것은 제한될 것으로 예상되며, 이에 따라 차량에 의한 병력 및 화물을 기동시키는 것이 제한될 것으로 예상된다. 육군 항공부대는 지형적인 요소의 제한사항을 극복할 수 있고, 단시간 내에 적에게 치명적인 타격을 줄 수 있는 결정적인 지점에 병력과 화물 등을 기동시킬 수 있는 장점이 있으므로, 전시 기동 헬기부대에 이러한 수송임무가 많이 부여될 것으로 예상된다. 따라서, 본 연구에서는 기동헬기부대에서 주어진 임무를 가장 빨리 수행할 수 있는 알고리즘 개발에 목표를 두었다.
소주제 1에서는 주어진 임무를 각 항공기에 할당하고, 항공기별 할당된 임무의 수행순서를 동시에 결정하는 스케줄링 문제를 다루었다. 특히, 주어진 임무가 항공기 한 대의 능력 (공간 및 무게)을 초과하는 경우, 그 임무는 여러대의 항공기로 나누어서 수행되며, 이 때 임무를 수행하는 항공기들은 항공기의 생존성 보장을 위하여 동시에 임무를 수행해야 하는 제한사항을 고려하고 있다. 본 소주제에서는 미션의 순서가 주어졌을 때, 스케줄을 만드는 두 가지 방법을 제안하였으며, 이러한 방법을 이용한 2단계 (two-phase) 발견적 기법 (heuristic)들을 제안하였다. 특히, 1단계에서는 병목중심 방법 (bottleneck-focused heuristic), 2단계에서는 병합된 지역탐색 기법 (local searches, i.e., interchange and insertion)이 효과적인 것을 확인하였다.
소주제 2에서는 소주제 1과 달리 임무가 항공기 조종사의 비행기술, 경험 등을 고려 이미 조종사 (항공기)에 할당되었다는 가정 하에 항공기별 주어진 임무의 수행 순서를 결정하는 스케줄링 문제를 다루었다. 본 소주제에서는 최적해 (optimal solution)을 구하기 위하여 분지한계법 (branch-and-bound algorithm)을 개발하였다. 분지한계법에서는 최적해의 우월 성질 (dominance property), 하한 (lower bound) 계산방법과 발견적 방법을 이용한 상한 (upper bound)을 구하는 방법을 제안하였다. 제시된 분지한계법은 중간 크기 문제까지 적당한 시간 내에 최적해를 주었으며, 또한 제안한 발견적 기법은 실제 크기의 문제까지 빠른 시간 내에 좋은 해를 주었다.
제시된 알고리듬의 성능 분석을 위하여 실전 상황을 고려하여 실험 문제를 생성하였으며, 제시된 알고리듬은 상용패키지인 CPLEX 12.1을 활용하여 비교 분석을 실시하였다. 실험 결과, 제안된 알고리듬은 논문에서 다루고 있는 문제에 대해서 합리적인 시간 내에 최적해 내지는 우수한 해를 찾아낼 수 있음을 확인하였다. 또한, 개발된 알고리듬은 기동 헬기부대의 작전 수행간 항공기 임무 할당 및 수행 순서 결정 방법으로 사용가능 할 것으로 예상된다.
