Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.42 No.1 pp.143-150
DOI : https://doi.org/10.11627/jkise.2019.42.1.143

Exact Algorithm for the Weapon Target Assignment and Fire Scheduling Problem

Young-Ho Cha^*

, BongJoo Jeong^**†

^*BCTP(Battle Command Training Program), Republic of Korea Army, Korea
^**Department of Industrial and Management Engineering, Hannam University

Corresponding Author : jbj@hnu.kr

Received 20/02/2019 Finally Revised 08/03/2019 Accepted 12/03/2019

Abstract

We focus on the weapon target assignment and fire scheduling problem (WTAFSP) with the objective of minimizing the makespan, i.e., the latest completion time of a given set of firing operations. In this study, we assume that there are m available weapons to fire at n targets (> m). The artillery attack operation consists of two steps of sequential procedure : assignment of weapons to the targets; and scheduling firing operations against the targets that are assigned to each weapon. This problem is a combination of weapon target assignment problem (WTAP) and fire scheduling problem (FSP). To solve this problem, we define the problem with a mixed integer programming model. Then, we develop exact algorithms based on a dynamic programming technique. Also, we suggest how to find lower bounds and upper bounds to a given problem. To evaluate the performance of developed exact algorithms, computational experiments are performed on randomly generated problems. From the results, we can see suggested exact algorithm solves problems of a medium size within a reasonable amount of computation time. Also, the results show that the computation time required for suggested exact algorithm can be seen to increase rapidly as the problem size grows. We report the result with analysis and give directions for future research for this study. This study is meaningful in that it suggests an exact algorithm for a more realistic problem than existing researches. Also, this study can provide a basis for developing algorithms that can solve larger size problems.

Key Words : Military , Fire scheduling , Branch and bound

표적 할당 및 사격순서결정문제를 위한 최적해 알고리즘 연구

차 영호^*, 정 봉주^**†

^*대한민국 육군 전투지휘훈련단
^**한남대학교 산업경영공학과

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

전투 상황에서 포격 작전 계획시, 일반적으로 적군 표 적물에 대한 정보(위치, 특성 등)가 이미 입수되어 있으 며 이를 바탕으로 작전수행 전에 미리 작전 계획을 준비 하게 된다. 포격 작전 계획 시 이러한 표적물에 대한 야 전 포병 부대의 사격을 수행하기 위해서는 아군 포병부 대에 적군 표적물을 할당하고, 각 포병부대에 할당된 목 표물들의 사격 순서, 즉, 사격일정계획을 수립하는 것이 필요하다.

이처럼 포격 작전 계획 수립은 두 번의 순차적 단계로 실행된다. 첫 번째, 임무 할당 단계에서는 적 목표물이 아군의 포병 부대나 포병 부대 그룹에 배정된다. 여기서 포병부대란, 포격작전을 수행하는 기본 부대로서 일반적 으로 6개의 포병대들로 구성되어 있다. 사용 가능한 포 병부대보다 더 많은 표적이 있을 경우, 한 개의 포병부대 가 하나 이상의 표적에 할당되는 경우도 고려해야한다. 두번째, 사격 일정 수립 단계에서는 각 포병부대에 할당 된 목표물에 대한 사격 순서를 결정한다. 표적은 하나 이 상의 포병부대에 배정될 수 있으며, 만약 어떤 표적에 여 러 포병부대가 배정되어 있다면 함께 지정된 포병부대 그룹은 해당 표적에 대한 사격 시 기습 효과를 얻기 위 해 동시에 사격을 실시하는 것을 원칙으로 한다.

첫 번째 단계에서 수행되는 임무 할당 문제는 사격부대 와 표적 간 할당문제(Weapon Target Assignment Problem; WTAP)로 구분되며, 두 번째 단계에서 수행되는 각 포병 부대에서의 표적 사격 순서를 결정하는 문제는 사격일정 계획문제(Fire Scheduling Problem; FSP)로 구분될 수 있다. 본 연구에서는 이 두 단계를 같이 고려하여 표적할당과 사격순서를 함께 정하는 표적할당 및 사격순서결정문제 (Weapon Target Assignment and Fire Scheduling Problem; WTAFSP)를 다루었다. 제 2장에서는 본 문제 연구에 참고 할만한 문헌 연구를 소개하였고 제 3장에서는 문제상황 을 수리모형을 통해 보다 상세히 정의하였다. 제 4장에서 는 본 연구에서 개발한 최적솔루션 알고리즘을 제시하였 으며 이 알고리즘에 대한 성능평가 실험 결과를 제 5장에 서 설명하였다. 제 6장에서는 최종적인 연구의 결과를 설 명한다.

2. 문헌 연구

먼저 사격일정계획(FSP)에 대한 문헌연구를 살펴보면, 이에 대한 연구가 매우 드물다는 것을 알 수 있다. FSP 를 처음 소개한 Kwon et al.[22]는 표적이 고정(이동하지 않음)되어 있다는 가정하에 최대사격종료시간(makespan) 을 최소화하는 FSP를 연구하였다. 그들은 최대사격종료 시간을 최소화하는 것을 통해 기습적인 공격 효과를 달 성하는 데 초점을 맞추었다. Kim and Lee[19]도 동일한 FSP를 연구하였으며 휴리스틱 알고리즘을 제시하였다. Kim and Lee[18]는 표적공유 상황에서 사격부대에서의 사격순서 결정 문제를 연구하였으며 이에 대해 휴리스틱 알고리즘을 제시하였다. Cha and Bang[5]은 FSP 문제에 최적해를 구하기 위한 분지한계법을 연구하였다. Choi et al. [8]은 아군에 대한 적의 위협을 최소화하기 위한 단일 사 격부대 문제에 대해 강건최적화 모델을 제시하였다. Choi and Lee[9]는 가중 사격 종료시간을 최소화하는 FSP 문 제에 대해 유전자 알고리즘을 제시하였다.

FSP에 관한 문헌이 부족하기 때문에, FSP 문제와 유사 한 특성을 공유하는 다중 프로세서 작업 일정계획 문제 (Multiprocessor Task Scheduling Problem; MTSP)에 대해 문헌 연구를 찾아보면 다음과 같다. MTSP는 Bozoki et al. [3]가 제일 처음 소개하였다. 그러나, 컴퓨팅 능력이 엄청 나게 증가하는 1990년대 전까지는 해당 연구 분야가 많 은 관심을 끌지 못했다. 그 후 Drozdowski[12] 및 Lee et al. [24]의 서베이 논문에 다양한 MTSP에 문제가 소개되었다. MTSP 문제는 문헌에서 Pk|fix|Cmax로 표시된다[15]. Pk| fix|Cmax 문제의 타당성 검증(feasibility)과 근사성에 대한 연구는 많은 연구들이 수행되었다. P2|fix|Cmax 문제는 전 형적인 2개 설비간의 작업일정계획 문제의 일반화된 버 전이다[13]. 따라서 MTSP도 NP-hard이다. Chen et al.[7] 은 P2|fix|Cmax 문제에 대해 다항 시간 근사 알고리즘을 개발하였다. 또한 Blazewicz et al.[2]은 P3|fix|Cmax 문제 에 대해 4/3배 비율의 다항시간 근사 알고리즘을 개발하 였고, Dell’Olmo et al.[11]은 이를 더 개선하여 동일 문제에 대해서 5/4 비율의 근사 알고리즘을 개발하였다. Goemans [14]은 해당 문제에 대해서 7/6배 비율의 근사 알고리즘 을 제시하였다. 그리고, Amoura et al.[1]은 Pk|fix|Cmax(k 는 고정된 모든 정수) 문제에 대해서 다항시간 근사 알고 리즘을 제시하였다. Huang et al.[16]은 P4|fix|Cmax에 대 해서 기존의 2배 비율의 근사 알고리즘을 크게 개선한 3/2배 비율의 근사 알고리즘을 제시하였다.

표적할당문제(Weapon Target Assignment Problem; WTAP) 에 관한 연구는 Manne[27]의 연구에서부터 시작되었다. 1960년과 70년대에는 다양한 연구자들로부터 연구가 수행 되었다. Taylor and Walsh[28]는 가용한 전체 자원을 포병 부대에 할당하고 살아남은 표적들의 가치를 최소화할 수 있는 할당 문제에 대해 연구하였다. Day[10]은 다양한 포 병부대 타입을 고려하여 보다 복잡한 표적에 대한 사격 문제에 대해 연구를 하였다. Lloyd and Witsenhausen[26] 은 WTAP 문제가 NP-Complete임을 보였다. Karasakal[17] 는 동맹군이 상황 인식 시스템을 가지고 있는 상황을 고려 하여 연구를 진행하였다.

Kwon et al.[21]과 Kwon et al.[23]는 사격임무를 마치기 위해 필요한 라운드의 수에 선형적인 형태의 사격 비용을 최소화 하는 것을 목표로 하는 WTAP를 연구하였다. Li et al.[25]는 WTAP 문제에 대해 분해 기법에 기반을 둔 다중 목적 진화 알고리즘(multiobjective evolutionary algorithm) 을 개발하였다. 또한 Chang et al.[6]는 동적 WTAP 문제에 대한 개미집단알고리즘을 제시하였다. Cetin and Esen[4] 는 WTAP 문제를 광고산업에서 예산과 광고 미디어 간에 할당 문제로 전환하여 연구를 수행하였다. WTAP 문제에 대한 다양한 알고리즘과 수리모형에 대한 리뷰는 Kline et al. [20]에서 찾아볼 수 있다.

본 연구에서 우리는 WTAP와 FSP가 동시에 존재하는 문제에 대해 연구를 수행하였다. 이에 대한 연구는 문제 의 복잡성이 매우 높고, 그로 인해 우리가 알고 있는 바 로는 아직 연구가 수행된 바가 없다. 우리는 본 문제에 대해서 수리모형과 함께 동적계획법과 분지한계법을 조 합한 최적 솔루션을 구하는 알고리즘을 개발하였다.

3. 문제 정의 및 설명

앞서 언급했다시피, 아군 포병부대의 사격 계획을 수 립하기 위해서는 표적을 아군 포병부대에 할당하고, 할 당된 표적들의 사격 순서를 수립해야 한다. 사격 계획을 수립하는데 핵심요소는 아군 포병부대와 표적, 그리고 사격시간이다. 여기서 사격시간은 사격을 진행(지속)하 는 시간을 의미한다.

포병부대 사격을 위한 최소 단위로써 일반적으로 곡사포 6문으로 구성된 부대를 의미함

period 단위 시간(사격 임무의 시간 단위를 시스템내 서로 다른 무기들 간에 동기화하기 위해 필요 한 사격 최소 단위 시간)

본 연구에서는 아래의 가정 사항을 가지고 있다.

1) 표적의 위치는 이미 알려져 있다.
2) 각 무기들은 단일 period 내에서는 최대 한 개의 표적만 공격 가능하다.
3) 사격 중 선점(preemption)은 허용되지 않는다.
4) 만약 표적이 하나 이상의 포병부대에 할당되어 있다면, 포병부대들은 해당 표적을 사격을 동시에 시작해야 한 다. 이는 기습공격에 의한 효과를 극대화하기 위해 필 요하다. 그러나 사격 종료 시점은 부대간에 서로 다를 수 있다.
5) 표적의 수는 포병부대의 수보다 많다. 그럼으로 하나의 포병 부대는 하나 이상의 표적에 할당될 수 있다.
6) 사격시간은 period의 정수 배로 정의한다.

본 연구에서는 아래의 표기법을 사용하여 연구를 수 행하였다.

인덱스와 파라메터(Indices and Parameters)

i 포병부대의 인덱스(i = 1, …, m)
j 표적의 인덱스(j = 1, …, n)
l 사격순서에서 순서를 표현하는 인덱스
W 포병부대의 집합
T 표적의 집합
A 아크의 집합, 만약 포병부대 i가 표적 j를 사격할 수 있으면 (i, j) ∈ A
d_j 표적 j를 파괴하기 위해 최소로 요구되는 확률, 0 < d_j < 1
p_ij 포병부대 i가 단일 period동안 사격하여 표적 j를 파 괴할 확률
M 매우 큰 수

결정 변수(Decision variables)

s_ij 포병부대 i가 표적 j를 향한 사격 시작 시점
c_ij 포병부대 i가 표적 j를 향한 사격을 종료하는 시점
y_ijl 만약 포병부대 i가 표적 j를 l번째 임무로 사격을 하면 y_ijl =1, 그렇지 않으면 y_ijl = 0.
x_ij 포병부대 i가 표적 j를 사격할 때 사격시간(period 수)

위의 표기법을 토대로 본 문제는 아래와 같은 비선형 정수계획 문제로 구성할 수 있다.

Minimize C_max

subject to

\begin{matrix} C_{max} \geq c_{i j} & \forall i, j \end{matrix}

(1)

\begin{matrix} 1 - Π_{\{i \in W |(i, j) \in A\}} {(1 - p_{i j})}^{x_{i j}} \geq d_{j} & \forall j \end{matrix}

(2)

\begin{matrix} s_{i j} = s_{h j} & \forall h \neq i, \forall j \end{matrix}

(3)

\begin{matrix} c_{i j} = s_{i j} + x_{i j} & \forall i, j \end{matrix}

(4)

\begin{matrix} c_{i j} - M (1 - y_{i j l}) \leq s_{i k} + M (1 - y_{i k l + 1}) & \forall i, j, k, l \end{matrix}

(5)

\begin{matrix} M \times \sum_{l} y_{i j l} \geq x_{i j} & \forall i, j \end{matrix}

(6)

\begin{matrix} \sum_{j} y_{i j l + 1} \leq \sum_{j} y_{i j l} & \forall i, l \end{matrix}

(7)

\begin{matrix} \sum_{j} y_{i j l} \leq 1 & \forall i, l \end{matrix}

(8)

\begin{matrix} \sum_{l} y_{i j l} \leq 1 & \forall i, j \end{matrix}

(9)

\begin{matrix} y_{i j} \in \{0, 1\} s_{i j}, c_{i j}, x_{i j} \geq 0 과 정수 & \forall i, j, l \end{matrix}

(10)

수리모형에서, 목적식은 모든 사격 임무를 다 마무리 하는 시점, 즉 최대사격종료시점을 최소로 하는 것을 목적 으로 한다. 이는 일반적인 일정계획 문제에서 최대작업 종료시점(Makespan)을 최소로 하는 것과 동일하다. 제약 조건 (2)은 사격시간에 따른 표적 j의 파괴될 확률을 정 의하고 이 확률이 표적파괴를 위한 최소요구사항 이상을 가지도록 설정한다. 제약조건 (3)은 서로 다른 포병부대 가 동일한 표적을 사격할 경우에는 동시에 사격을 시작 하도록 설정한다. 제약조건 (4)는 사격시작시점과 사격시 간, 그리고 사격종료시점 간의 관계를 설정한다. 제약조 건 (5)는 각 사격부대의 사격 임무들 중 연속된 사격 임 무들 간의 사격시작 및 종료시점을 정의한다. 제약조건 (6)은 표적 j가 포병부대 i에 할당되었을 때, 표적 j가 포 병부대 i의 사격 순서에 한 번만 배치되어야 함을 의미 한다. 제약조건 (7)은 각 포병부대의 사격순서에서 l순서 에 사격 임무가 있어야만 (l+1)에 사격임무가 배치될 수 있음을 의미한다. 제약조건 (8)과 (9)는 포병부대 i의 한 사격순서에는 한 표적만 배치될 수 있으며, 포병부대에 할당된 표적은 그 포병부대의 사격 순서 중 한 곳에만 배치 가능하다는 것을 의미한다.

비선형 제약조건 (2)은 Kwon et al.[21]의 연구에서처 럼 로그 함수를 이용하여 아래와 같이 선형식으로 변형 가능하다.

\sum_{\{i \in W |(i, j) \in A\}} x_{i j} ln (1 - p_{i j}) \leq ln (1 - d_{j}), \forall j

그리고, 파라메터 β(본 연구에서는 10으로 설정하였 음)를 양변에 곱하고 내림함으로 다음의 제약조건 (2’)으 로 근사화 할 수 있다.

\sum_{\{i \in W |(i, j) \in A\}} a_{i j} x_{i j} \geq b_{j} \forall j

(2’)

여기서 $a_{i j} = ⌊- β ln (1 - p_{i j})⌋ > 0, b_{j} = ⌊- β ln (1 - d_{j})⌋ > 0$ 로 설정한다. 이 근사화 방법은 p_ij와 d_j가 확률적인 추정을 기반으로 하고 있기 때문에 현실적인 관점에서는 충분히 납득할 만하다. 이것은 정수 계수를 가진 실현 가능한 영 역의 근사치를 제공하고 비선형 정수 프로그래밍 모델을 정수 프로그래밍 모델로 변환한다.

4. 최적해 알고리즘

본 장에서는 현실적으로 가장 많이 풀게 되는 두 개 또 는 세 개 포병부대가 있는 작은 사이즈의 문제에 대한 최 적 알고리즘을 제시한다. 알고리즘은 2단계, 즉, 포병부대 에 표적을 할당하는 단계와 각 포병부대에서 사격순서를 정하는 단계로 구성된다. 첫 번째 단계의 목적은 각 사격 포병부대에 할당된 사격 임무들의 사격시간 총합들 중 최 대시간을 최소화하는 것이다. 즉, ${max}_{i = 1, \dots, m} (\sum_{j = 1}^{n} x_{i j})$ 을 최소화하는 것을 목표로 한다. 첫 번째 할당단계에서 우리 는 두 번째 단계에서 수행되는 사격순서 일정계획 의사결 정은 전혀 고려하지 않고 진행한다. 그래서 할당단계 결과 에서는 사격순서 일정계획 의사결정으로 인해 발생할 수 있는 유휴시간(idle time)은 전혀 포함되지 않는다. 이러한 개념은 할당문제의 최적 솔루션이 전체 문제(WTAFSP)의 하한(lower bound) 값을 제시할 수 있음을 의미한다. 표적 을 각 포병부대에 할당한 이후, 두 번째 단계에서 최대사 격종료시간을 최소화할 수 있는 사격 순서를 찾는다. 이 단계에서 우리는 Cha and Bang[5]이 제시한 분지한계법을 사용하였다. 본 알고리즘을 통해서 얻은 해답은 WTAFSP 의 최적해를 구하기 위한 상한(upper bound)으로 활용된 다. 알고리즘의 상세한 사항은 다음과 같다.

4.1 두 개 포병부대 문제에 대한 동적계획법 (Dynamic programming; DP) 알고리즘

전진형 동적계획법(Forward DP) 알고리즘은 두 개의 포병부대에 대해 n개의 표적이 있는 문제를 풀기 위해 개발되었다. 모든 표적 j에 대해서 w(j)와 D₀를 다음과 같이 정의한다.

w (j) = ⌈b_{j} / m a x (a_{i j})⌉, D_{0} = \sum_{j = 1}^{n} w (j) \forall j

여기서, a_ij와 b_j는 제약조건 (2′)에서 언급되었으며, 따라서 w(j)는 표적 j가 오직 하나의 포병부대에 할당되 었을 때 최소사격시간을 의미한다. D^*를 할당문제에서의 최적 솔루션의 목적값으로 정의한다. 그리고 DP알고리 즘의 탐색 공간을 줄이기 위해 다음의 Lemma를 도출하 였다.

Lemma 1. $D_{0} / 2 \leq D^{*} \leq D_{0}$ .

Proof. $x_{i j}^{*}$ , i = 1, 2, j = 1, …, n를 할당문제 최적해라고 가정한다. 각 표적에서 제약조건 (2’)에 의해서 $\sum a_{i j} x_{i j} \geq b_{j}$ 와 $b_{j} / m a x (a_{i j}) \leq \sum a_{i j} x_{i j} / max (a_{i j}) \leq \sum x_{i j}$ 식이 만족된다. 그래서 $w (j) = ⌈b_{j} / m a x (a_{i j})⌉ \leq ⌈\sum x_{i j}⌉$ 가 만족되며, 이것은 할당문제 최적해를 포함하는 어떠한 할당해에서도 w(j)가 포병부대-1의 사격시간 (x_1j)과 포병부대-2의 사격시간 (x_2j) 합보다 작거나 같다는 것을 의미한다. 즉, $w (1) \leq x_{11}^{*} + x_{21}^{*}, w (2) \leq x_{12}^{*} + x_{22}^{*}, \dots, w (n) \leq x_{1 n}^{*} + x_{2 n}^{*}$ 를 의미한다. 해당 부 등호에서 왼쪽항과 오른쪽 항을 각각 합하면 $\sum w (j) \leq \sum x_{1 j}^{*} + \sum x_{2 j}^{*}$ 식을 구할 수 있다. 여기서 우리는 다음의 두 가 지 경우를 고려해야 한다. (1) 할당 문제의 최적해의 목적 값(각 포병부대의 사격시간 총합들 중 최대값)이 포병부대 -1에 의해 최종적으로 정해지는 경우, (2) 할당 문제의 최 적해의 목적값이 포병부대-2에 의해 최종적으로 정해지는 경우이다. 첫 번째의 경우, $\sum x_{1 j}^{*} \geq \sum x_{2 j}^{*}$ 이다. 그리고 $\sum w (j) / 2 \leq (\sum x_{1 j}^{*} + \sum x_{2 j}^{*}) / 2 \leq \sum x_{1 j}^{*} = D^{*}$ 가 성립된다. 두 번째 의 경우, 첫 번째 경우와 같은 절차로 적용하면 $\sum w (j) / 2 \leq D^{*}$ 임을 알 수 있다. 따라서 증명이 완료된다. $D^{*} \leq D_{0}$ 에 대한 증명은 여기에 생략하도록 한다. ■ DP 알고리즘을 설명하기 위해서 다음과 같은 표기법 을 사용한다.

j DP의 stage에서의 표적의 인덱스(j = 1, …, n)
x_ij 표적 j에 대한 포병부대 i의 사격 임무의 사격시 간(period 수)
X_j 표적 j에 대한 제약조건(2’)를 만족하는 할당 벡 터들의 세트, $x_{j} = {(x_{1 j}, x_{2 j})}^{T}$
f_j(a, b) 포병부대-1의 사격시간의 합이 a이고 포병부대-2 의 사격시간의 합이 b일 때, 표적 1, …, j에 대한 최적 할당해의 목적값

경계조건(Boundary conditions) :

$\begin{array}{l} f_{j} (a, b) = \infty . \forall a, b, j \\ f_{0} (0, 0) = 0. \end{array}$

재귀방정식(Recursive equations) :

for j = 1, …, n, a = 0, …, D₀, and b = 0, …, D₀

$\begin{array}{l} f_{j} (a, b) = \\ min_{(x_{1 j}, x_{2 j}) \in X_{j}} [max{G_{j - 1} (a - x_{1 j}) + x_{1 j}, H_{j - 1} (b - x_{2 j}) + x_{2 j}}] . \end{array}$

$G_{j - 1} (a - x_{1 j}) : f_{j - 1} (a - x_{1 j}, b - x_{2 j})$ 에서 포병부대-1의 사격시간의 합

$\{\begin{array}{l} \infty & if (a - x_{1 j}) < 0 or f_{j - 1} (a - x_{1 j}, b - x_{2 j}) = \infty \\ (a - x_{1 j}) & o t h e r w i s e \end{array}$

$H_{j - 1} (b - x_{2 j}) : f_{j - 1} (a - x_{1 j}, b - x_{2 j})$ 에서 포병부대-2의 사격시간의 합

$\{\begin{array}{l} \infty & if (b - x_{2 j}) < 0 or f_{j - 1} (a - x_{1 j}, b - x_{2 j}) = \infty \\ (b - x_{2 j}) & o t h e r w i s e \end{array}$

$T h e s o l u t i o n : min_{\forall (a, b)} \{f_{n} (a, b)\}$

DP의 연산복잡도는 Lemma 1에서와 같이 D₀를 정의할 때 $O (n D_{0}^{2})$ 로 정의된다. f_n(a, b)에 해당하는 할당 벡터는 역추적 방식에 의해 구성되어지며 이에 대한 시간복잡도 는 O(n)이다.

4.2 세 개 포병부대 문제에 대한 동적계획법(Dynamic programming; DP) 알고리즘

세 개의 포병부대의 FSP를 대상으로 한 DP 알고리즘 을 위해 유사한 방법이 수행될 수 있다. 모든 포병부대 i 에 대해서 w(j)와 D₀를 다음과 같이 정의한다.

w (j) = ⌈b_{j} / m a x (a_{i j})⌉, D_{0} = \sum_{j = 1}^{n} w (j) \forall j

D^*를 할당문제에서의 최적 솔루션으로 정의한다. 그리고 Lemma 1에서처럼 우리는 $D^{*} \leq D_{0}$ 를 토대로 DP알고리 즘의 탐색공간을 줄일 수 있다. DP 알고리즘을 설명하기 위해서 다음과 같은 표기법을 사용한다.

j DP의 단계에서의 표적의 인덱스(j = 1, …, n)
x_ij 표적 j에 대한 포병부대 i의 사격 임무의 사격 시간(period 수)
X_j 표적 j에 대한 제약조건 (2’)를 만족하는 할당 벡터들의 세트, $x_{j} = {(x_{1 j}, x_{2 j}, x_{3 j})}^{T}$
f_j(a, b, c) 포병부대-1의 사격시간의 합이 a, 포병부대-2 의 사격시간의 합이 b, 포병부대-3의 사격시간 의 합이 c일 때, 표적 1, …, j에 대한 최적 할 당해의 목적값

경계조건(Boundary conditions) :

$\begin{array}{l} f_{j} (a, b, c) = \infty \forall a, b, c, j \\ f_{0} (0, 0, 0) = 0 \end{array}$

재귀방정식(Recursive equations) :

for j = 1, …, n, a = 0, …, D₀, and b = 0, …, D₀

$\begin{array}{l} f_{j} (a, b, c) = \\ min_{(x_{1 j}, x_{2 j}, x_{3 j}) \in X_{j}} [max{G_{j - 1} (a - x_{1 j}) + x_{1 j}, H_{j - 1} (b - x_{2 j}) \\ + x_{2 j}, L_{j - 1} (c - x_{3 j})}] . \end{array}$

$G_{j - 1} (a - x_{1 j}) : f_{j - 1} (a - x_{1 j}, b - x_{2 j}, c - x_{3 j})$ 에서 포병부대-1의 사격시간 의 합

$\{\begin{array}{l} \infty & if (a - x_{1 j}) < 0 or f_{j - 1} (a - x_{1 j}, b - x_{2 j}, c - x_{3 j}) = \infty \\ (a - x_{1 j}) & o t h e r w i s e \end{array}$

$H_{j - 1} (b - x_{2 j}) : f_{j - 1} (a - x_{1 j}, b - x_{2 j}, c - x_{3 j})$ 에서 포병부대-2의 사격시간 의 합

$\{\begin{array}{l} \infty & if (b - x_{2 j}) < 0 or f_{j - 1} (a - x_{1 j}, b - x_{2 j}, c - x_{3 j}) = \infty \\ (b - x_{2 j}) & o t h e r w i s e \end{array}$

$L_{j - 1} (c - x_{3 j}) : f_{j - 1} (a - x_{1 j}, b - x_{2 j}, c - x_{3 j})$ 에서 포병부대-2의 사격시간 의 합

$\{\begin{array}{l} \infty & if (c - x_{3 j}) < 0 or f_{j - 1} (a - x_{1 j}, b - x_{2 j}, c - x_{3 j}) = \infty \\ (c - x_{3 j}) & o t h e r w i s e \end{array}$

$T h e s o l u t i o n : min_{\forall (a, b, c)} \{f_{n} (a, b, c)\}$

DP의 연산복잡도는 Lemma 1에서와 같이 D₀를 정의할 때 $O (n D_{0}^{3})$ 로 정의된다. f_n(a, b, c)에 해당하는 할당 벡터 는 역추적 방식에 의해 구성되어지며 이에 대한 시간복 잡도는 O(n)이다.

4.3 DP 기반 알고리즘 전체 개요

이제 우리는 두 개 또는 세 개 포병부대를 포함하는 WTAFSP를 풀기 위한 최적해 알고리즘을 제시한다. 이 알고리즘은 포병부대에 표적을 먼저 할당하는 첫 번째 단계와 각 포병부대에서 사격 순서를 정하는 두 번째 단 계로 구성된다. 첫 번째 단계인 할당 문제에서는, 본 연 구에서 개발한 DP 알고리즘을 사용한다. 첫 번째 단계에 서 결과로, 각 포병부대 j(j = 1, …, n)의 최적 할당 백터 (x_j’s)가 생성된다. 두 번째 단계인 사격순서 결정 문제에 서는 Cha and Bang[5]이 제시한 분지한계법 알고리즘을 첫번째 단계에서 구한 각 표적의 할당 벡터를 대상으로 적용하여 최적해를 찾는다. 동일한 재귀(recursive) 함수 값을 가지고 있는 두 개의 할당 백터가 서로 다른 사격 순서와 서로 다른 WTAFSP 목적값(최대사격종료시간)을 가질 수 있음을 주의해야한다.

첫 번째 단계에서 구한 최적 할당 백터에 분지한계법 을 적용하여 초기해가 구해진다. 이렇게 구한 초기해는 전체 WTAFSP 최적해의 상한값(upper bound)으로 사용 될 수 있다. 또한, 첫 번째 단계에서 DP 알고리즘을 통 해 구한 최적 재귀 함수 값은 하한값(lower bound)으로 사용될 수 있다. 여기서 첫 번째 단계에서는 사격순서로 인해 발생하는 유휴시간이 고려되지 않기 때문에 하한값 으로 사용될 수 있음을 기억한다. 만약 상한과 하한이 동 일하다면, 현재의 할당해와 사격순서가 WTAFSP의 최적 해가 된다. 그렇지 않다면, 우리는 재귀 함수 값이 상한 보다 적고 하한보다 큰 모든 가능한 할당 벡터를 생성하 고, 각 할당 벡터를 대상으로 최적사격 순서를 분지한계 법을 통해 구한다. 여기서 우리는 현재 상한값보다 해의 목적값이 큰 대안은 고려하지 않는다.

5. 알고리즘 실험

제시한 알고리즘의 성능을 평가하기위해서, 우리는 한 국의 실제 상황을 잘 고려할 수 있도록 있는 무작위 문 제를 생성하였다. 실제 상황에서 하나의 포병 대대는 3 개의 포병부대로 구성된다.

본 연구에서 사용된 모든 알고리즘은 C 언어를 통해 프로그래밍 되었으며 모든 실험은 2.8GHz CPU Clock 속 도를 가지는 펜티엄 4 컴퓨터로 수행되었다. 그리고 실 험의 상한 시간은 3,600초로 설정하여 수행하였다. 각 실 험에서 사용한 a_ij, b_j 값은 [2, 6]와 [10, 20]인 균일분포 를 통해 각각 생성을 하였다.

먼저, 제시한 알고리즘의 성능을 테스트하기 위해 우 리는 ILOG CPLEX 11.0을 벤치마크 대상으로 사용하였 다. 실험을 위해 우리는 2개 수준의 사격포병 부대 수(2, 3개 부대)와 5개 수준의 표적 수(2, 4, 6, 8, 10개 표적)를 설정하고 이들의 조합에 대해 각 5개의 문제, 총 50문제 를 생성하였다. 이 실험에 대한 결과는 <Table 1>에서 보여 진다. <Table 1>에서 평균 연산시간(average computational time)과 상한시간(3,600초) 안에 최적해를 풀지 못한 문제 수를 알 수 있다. 50개 문제 중 2, 4개 표적 문 제를 제외한 모든 문제에서 CPLEX는 주어진 시간 내에 풀어내지 못했다. 그러나 본 연구에서 제시한 최적 알고 리즘은 모든 문제에 대해서 주어진 시간 안에 최적해를 구해낼 수 있었다.

최적해 알고리즘의 추가적인 실험을 위해서, 2개 수준 의 포병부대 수(2, 3개 포병부대)와 6개 수준의 표적 수 (10, 12, 14, 16, 18, 20개 표적)에 대해 각 조합별로 5개 의 문제, 즉, 총 60문제를 생성하여 실험을 수행하였다. 해당 결과는 <Table 2>에 나와 있다. 이번 실험에서는, 우리는 중간 사이즈의 표적 수를 가진 문제에 대해서 최 적해 알고리즘이 문제를 풀어 낼 수 있는 것을 확인하였 다. 그러나 포병부대 수가 늘고 표적의 수가 늘수록 연산 시간이 급격히 늘어남을 알 수 있다. 따라서 매우 큰 사 이즈의 문제를 풀어내기 위해서는 추가적인 연구가 필요 하다고 할 수 있다.

6. 결 론

이 장에서는 최종 사격종료시간을 최소화하기 위해 표적을 포병부대에 할당하고 사격순서를 정하는 휴리스 틱 알고리즘을 제시하였다. 우리는 동적계획법(Dynamic programming; DP) 방법론에 기반한 2단계로 이루어진 최적해 도출 알고리즘을 개발하였다. 해당 알고리즘에서 1단계에서는 DP 알고리즘을 통해 표적을 포병부대에 할 당하고, 2단계에서는 1단계 결과를 바탕으로 분지한계법 을 사용하여 포병부대의 사격 순서 결정한다. 실험을 통 해서 본 연구에서 제시한 알고리즘을 CPLEX와 비교하 여 그 효율성을 입증하였다. 이 연구는 다양한 방향으로 확장이 가능하다. 예를 들어, 해의 질적 수준을 개선하기 위한 더 많은 최적해 특성을 개발할 수도 있으며, 또한 보다 복잡하고 큰 사이즈의 문제를 다루기 위한 다양한 메타휴리스틱 알고리즘, 즉 유전자 알고리즘(GA), 담금 질 기법(SA) 같은 알고리즘을 개발할 수도 있다. 본 연 구는 기존 연구보다 훨씬 현실적인 문제에 대해 최적 알 고리즘을 제시하였다. 본 연구에서 제시한 상한, 하한 그 리고 방법론은 추후 보다 복잡하고 큰 사이즈 문제를 위 한 알고리즘을 연구할 때 초석이 될 것으로 기대한다.

Figure

Table

<Table 1>.

Computation Time of CPLEX and Exact Algorithm

<Table 2>.

Result of the Exact Algorithm

Reference

Amoura, A.K., Bampis, E., Kenyon, C., and Manoussakis, Y., Scheduling independent multiprocessor tasks, Algorithmica, 2002, Vol. 32, No. 2, pp. 247-261.
Blazewicz, J., Dell’Olmo, P., Drozdowski, M., and Speranza, M., Scheduling multiprocessor tasks on three dedicated processors, Information Processing Letters, 1992, Vol. 41, No. 5, pp. 275-280.
Bozoki, G. and Richard, J.P., A branch and bound algorithm for the continuous-process job-shop scheduling problems, AIIE Transactions, 1970, Vol. 2, No. 3, pp. 246-252.
Cetin, E. and Esen, S.T., A weapon-target assignment approach to media allocation, Applied Mathematics Computation, 2006, Vol. 175, No. 2, pp. 1266-1275.
Cha, Y.-H. and Bang, J.-Y., A branch-and-bound algorithm to minimize the makespan in a fire scheduling problem, Journal of Society of Korea Industrial and Systems Engineering, 2015, Vol. 38, No. 4, pp. 132-141.
Chang, T., Kong, D., Hao, N., Xu, K., and Yang, G., Solving the dynamic weapon target assignment problem by an improved artificial bee colony algorithm with heuristic factor initialization, Applied Soft Computing, 2018, Vol. 70, pp. 845-863.
Chen, J. and Lee, C.-Y., General multiprocessor tasks scheduling, Naval Research Logistics, 1999, Vol. 46, No. 1, pp. 57-74.
Choi, Y.-B., Jin, S.-H., and Kim, K.-S., Deterministic and robust optimization approach for single artillery unit fire scheduling problem, Applied Sciences, 2017, Vol. 7, No. 10, 1038.
Choi, Y.-J. and Lee, I.-S., A fire sequencing problem to minimize the total weighted firing completion time of the artillery weapons, Industrial Engineering & Management Systems, 2018, Vol. 17, No. 2, pp. 249-258.
Day, R.H., Allocating weapons to target complexes by means of nonlinear programming, Operations Research, 1966, Vol. 14, No. 6, pp. 992-1013.
Dell’Olmo, P., Speranza, M.G., and Tuza, Z., Efficiency and effectiveness of normal schedules on three dedicated processors, Discrete Mathematics, 1997, Vol. 164, No. 1-3, pp. 67-79.
Drozdowski, M., Scheduling multiprocessor tasks-An overview, European Journal of Operational Research, 1996, Vol. 94, No. 2, pp. 215-230.
Garey, M.R. and Johnson, D.S., Computers and intractability : a guide to the theory of NP-completeness, 1979 (San Francisco : Freeman).
Goemans, M.R., An approximation algorithm for scheduling on three dedicated machines, Discrete Applied Mathematics, 1995, Vol. 61, No. 1, pp. 49-59.
Hall, L.A., Approximation algorithms for scheduling, 1997(PWS Publishing Company, pp 1-45).
Huang, J., Chen, J., Chen, S., and Wang, J., A simple linear time approximation algorithm for multi-processor job scheduling on four processors, Journal of Combinatorial Optimization, 2007, Vol. 13, No. 1, pp. 33-45.
Karasakal, O., Air defense missile-target allocation models for a naval task group, Computers & Operations Research, 2008, Vol. 35, No. 6, pp. 1759-1770.
Kim, D.-H. and Lee, Y.-H., The heuristic algorithm for the fire target allocation and sequencing problem, Proceedings of the 2008 spring KIIE conference, 2008, Pohang, Korea.
Kim, T.-H. and Lee, Y.-H., Fire sequencing problem with shared targets. Korean Operations Research and Management Society, 2003, Vol. 28, No. 3, pp. 123-134.
Kline, A., Ahner, D., and Hill, R., The weapon-target assignment problem, Computers and Operations Research, 2018, In Press.
Kwon, O.-J., Kang, D.-H., Lee, K.-S., and Park, S.-S., Lagrangian relaxation approach to the targeting problem, Naval Research Logistics, 1999, Vol. 46, No. 6, pp. 640-653.
Kwon, O.-J., Lee, K.-S., and Park, S.-S., Targeting and scheduling problem for field artillery, Computers & Industrial Engineering, 1997, Vol. 33, No. 3-4, pp. 693-696.
Kwon, O.-J., Lee, K.-S., Kang, D.-H., and Park, S.-S., A branch-and-price algorithm for a targeting problem, Naval Research Logistics, 2007, Vol. 54, No. 7, pp. 732-741.
Lee, C.-Y., Lei, L., and Pinedo, M., Current trends in deterministic scheduling, Annals of Operations Research, 1997, Vol. 70, pp. 1-41.
Li, X., Zhou, D., Pan, Q., Tang, Y., and Huang, J., Weapon-target assignment problem by multiobjective evolutionary algorithm based on decomposition, Complexity, 2018, Vol. 2018, p. 19.
Lloyd, S.P. and Witsenhausen, H.S., Weapons allocation is NP-complete, Proceedings of the 1986 Summer Conference on Simulation : NV, USA, pp. 1054-1058.
Manne, A., A target assignment problem, Operations Research, 1958, Vol. 6, No. 3, pp. 346-351.
Taylor, J.L. and Walsh, J.E., Planning by resource allocation methods-illustrated by military applications, Operations Research, 1964, Vol. 12, No. 5, pp. 693-706.