We examine a scheduling problem that assigns various ISR (Intelligence, Surveillance, and Reconnaissance) assets to the targets to be monitored for each time slot, that is, determines the target to be watched by each asset on each time. We first propose SR (Surveillance and Reconnaissance) Index that determines the surveillance and reconnaissance effectiveness of a pair of an ISR asset and a target. We use an AHP (Analytic Hierarchy Process) method to quantify amount of information acquired from the ISR assets and Army Combat Force Index for relative importance of the targets. We identify constraints and objectives as well as scheduling decisions. We then develop a mixed integer programming model for determining optimal scheduling decisions. The ISR scheduling problem is equivalent to an open-shop scheduling problem with preemption, which is known to be NP (Nondeterministic Polynomial Time)-hard problem. Due to the computational complexity and problem size, we develop an efficient heuristic scheduling rule called order-flow (OF), which assigns the pairs of ISR asset and target in the order of SR Index size. We also develop a genetic algorithm. We compare the computational performance of the three solution methods. Finally, by using OF scheduling rule, we examine the scheduling decisions and schedules to scenarios which are defined based on OP (Operation Plan) & IPB (Intelligence Preparation of the battlefield) data. We discuss validity of the proposed SR Index and scheduling model, examine the characteristics of the optimal ISR schedules, and derive insights and strategies for ISR asset scheduling.
매 이산시간 t에서 다양한 ISR(정보, 감시, 정찰) 자산이 관측해야할 목표를 결정, 할당하는 스케줄링 문제를 다룬다. 우선 ISR 자산과 대상의 감시 및 정찰 효과를 결정하는 SR(정참감시)-Index 제안한다. 또한 목표지역의 상대적 중요성을 결정하기 위해 육군 전투력 지수를 활용하고 ISR 자산으로부터 획득된 정보의 양을 정량화하기 위해 AHP(Analytic Hierarchy Process) 방법을 활용한다. 스케줄링을 결정하기 위해 전술교리, 작전계획(Operation Plan), 전장정보분석(Intelligence Preparation of the Battlefield) 등과 같은 다양한 제약사항을 반영한다. 이를 위해 최적의 스케줄을 산출하기 위해 MILP를 활용하여 모델을 개발하였다. ISR 스케줄링 문제는 NP-Hard한 문제로 알려진 open-shop scheduling problem with preemption 문제와 유사하다. 이를 해결하기 위해 ISR자산과 목표지역의 SR-Index가 높은 크기부터 감시 임무를 확정하는 순서 흐름(Order-Flow)라는 휴리스틱 스케줄링을 개발한다. 또한 유전자 알고리즘(GA) 개발하여 비교 분석한다. 마지막으로 OF 스케줄링 기법을 활용하여 특정 시나리오상 최적의 자산의 수량과 목표지역 개수를 확인하고, 다양한 시나리오를 반영한 실험을 통해 정보감시자산 운용에 대한 통찰력과 전략을 도출한다.
