In this thesis, we propose a Mixed integer programming model for countermaneuver support mission planning through parallel machine scheduling, and conduct a study to optimally schedule the missions assigned to the army engineer troops. In addition, the concept of cooperation by platoons is proposed to shorten the mission completion time by minimizing the imbalance of mission completion time for each engineer platoon. We propose experimental results that the mission completion time with consideration of cooperation is shorter than that without consideration of cooperation. Additionally, we confirm that cooperation is still effective in shortening the mission completion time, even if the capability is not at its maximum and is reduced by a certain ratio. Finally, since the parallel machine scheduling problem belongs to the NP-hard problem, we propose a solution approach using genetic algorithm in order to obtain a near optimal solution of a larger scale problem within a fast computation time.
본 논문에서는 병렬기계 일정계획방법을 통해 대기동지원임무 일정계획을 위한 혼합정수계획 모형을 제시하고, 공병 부대에 할당된 임무들의 일정을 최적으로 계획하기 위한 연구를 수행한다. 또한, 공병 전투소대별 임무 완료시간 불균형의 최소화를 통한 전체 대기동지원임무 완료시간 단축을 위해 소대 간 협업의 개념을 제시한다. 협업을 고려한 일정계획 시, 협업을 고려하지 않고 각 소대에 임무를 할당하는 경우에 비해 전체 임무 완료시간이 단축되는 것을 실험을 통해 확인한다. 또한 협업 시 능력을 최대로 발휘하지 못하고 일정 비율로 저하되는 경우에도 협업이 임무 완료시간 단축에 여전히 효과적임을 확인한다. 마지막으로 병렬기계 일정계획 문제가 NP-hard 문제에 속하므로, 더 큰 규모 문제의 최적에 가까운 해를 빠른 계산시간 내에 얻기 위해 유전 알고리즘을 이용한 문제 해결 방법을 제시한다.
