• Editorial Board +
• For Contributors +
• Journal Search +
Journal Search Engine
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.17 No.2 pp.249-258
DOI : https://doi.org/10.7232/iems.2018.17.2.249

# A Fire Sequencing Problem to Minimize the Total Weighted Firing Completion Time of the Artillery Weapons

Yu Jun Choi, Ik Sun Lee*
School of Business, Dong-A University, Busan, Republic of Korea
Corresponding Author, E-mail: lis1007@dau.ac.kr
January 6, 2016 August 26, 2016 January 24, 2018

## ABSTRACT

This paper studies the fire sequencing problem to minimize the total weighted firing completion time of artillery weapons, and provides effective and efficient solution methodologies to the problem. This paper considers the weapon system composed of various types of guns, and multiple targets to be destroyed. For the problem, a genetic algorithm is derived to provide efficient and effective solutions, and a branch-and-bound algorithm is also developed to find optimal solutions up to the medium-sized problems. Through the extensive computational tests, the performances of the proposed genetic and the branch-and-bound algorithms are evaluated.

## 1. INTRODUCTION

This paper considers a scheduling problem arising in the military, especially in the artillery operations. At the artillery operations in the weapon system, it is important to decrease the potential damage from the enemies, which needs the ability to neutralize and destroy earlier the weapons of the potential enemies. If the number of enemies increases, and if the variety of our weapon system increases, then the complexity of decision-making is dramatically increased. In this paper, the planned artillery attack operation is considered to study, which includes a set of targets to be destroyed and a set of weapons under a predetermined operation plan.

Gunpower of various weapon systems in the national defense field means a hitting form to do the enemy damage, and plays a decisive role weakening enemy combat power. The Korea's pattern of warfare is not a long war but a local military collision for about 30-60 minutes. The success of these counterfire warfares depends upon making an enemy unit lethargic in the initial round of the warfare, and it acts as an important factor deciding the outcome of a war. This makes a high-risk force of all enemy force inevitable early by gunpower, By doing so, the ability for the war fighting capability and C4I (Command, Control, Communication, Computer, and Intelligence) system will be improved out of the action temporarily, and it will be able to work vitally about the importance of gunpower. In this regard, the degree of risk means a weighted that are entitled according to a threatening degree to our army of all enemy unit, and it can reinterpret as a target unit to strike first when we manage gunpower.

In order to improve the weapon-power performance, the effectiveness and efficiency of decision-making process is very essential. The planned artillery operation consists of a sequential procedure of two steps: the first step is an allocation of targets to our weapons; and the second step is an establishment of a firing scheduling of the weapons for the targets. The decision issue of the first step is called the weapon target assignment problem (WTAP) introduced in Ahuja et al. (2007), and that of the second step is called the fire scheduling problem (FSP). Specifically this paper considers the FSP with a given set of weapons for a given targets to minimize the total threat from the enemies.

From now, the literature reviews related on this paper are presented. Matlin (1970) and Eckler and Burr (1972) have presented overall reviews on the WTAP. Firstly Manne (1958) has introduced the concept of the WTAP and solved the problem by use of the transportation problem, and Lloyd and Witsenhausen (1986) have proven that the WTAP is NP-hard. Hosein and Athans (1990) have considered a multi-stage version of the WTAP, and derived a heuristic which makes an allocation based on the assignment in the previous period. Christetal et al. (1993) and Erdem and Ozdemirel (2003) have presented a solution algorithm based on neural networks and a genetic algorithm, respectively. Kwon et al. (1999) have applied Lagrangian relaxation and a branch-andbound method to the WTAP. Lee and Lee (2003) have presented a hybrid algorithm composed of an ant colony and a genetic algorithm. On the other hand, Malcolm (2004) and Karasakal (2008) have considered the situation that the opponent’s behavior is taken into account, and established a solution model. The WTAP can be also applied for the advertisement industry for media allocation (Çetin and Esen, 2006), and for the medicine industry for cancer modeling (Esen et al., 2008).

On the other hand, researches on the FSP are relatively rare. Kwon et al. (1997) have firstly suggested the FSP with the objective of minimizing makespan, and derived a heuristic algorithm. Cha and Kim (2010) have considered the situation that targets may move and hence the destruction probability of each target decreases as time passes. They have presented a branch and bound algorithm with the objective of minimizing total threat of the targets, which is a function of the destruction probabilities of the targets.

This paper considers the fire sequencing problem to minimize the total weighted firing completion times of artillery weapons, where the weight of the target represents the threat from the target which may counterattack. If the weight of a target is larger than any other targets, then it means that the target is more threatening, and the target has to be destroyed more preferentially.

The fire sequencing problem in this paper can interpreted as a kind of the machine scheduling problem. Thus the targets can be jobs, and the artillery weapons can be machines, the required firing time can be the processing time of each job. The FSP in this paper seems to be similar to the multi-processor task scheduling problem (MPTSP) (Hoogeveen et al., 1994), in which each job need to be processed in one or more machines simultaneously. While each job requires the identical processing time on the machines in the MPTSP, the weapons can have different firing durations in the FSP in this paper, i.e. the processing times for each target. Thus it can be concluded that the MPTSP is a special case of the FSP, and in other words the FSP is more general case than the MPTSP. Hoogeveen et al. (1994) have proved that the MPTSP is NP-hard, so that the FSP in this paper is also NP-hard. This means that as the number of targets and artillery weapons increases, the problem complexity increases. Since we may face the FSP in the real-time combat situations, we need to develop effective and efficient solution methodologies to the problem. Therefore this paper derives first a genetic algorithm that finds more efficient solutions for the general situations, and presents a branch-and-bound algorithm for more effective attacking operations.

This paper is organized as follows. Section 2 defines the fire sequencing problem and presents mathematical formulation. Section 3 proposes a genetic algorithm that can find efficient solution. Section 4 derives a branchand- bound algorithm with lower bounds and a simple heuristic algorithm. In Section 5, the performance of the derived algorithms is evaluated through extensive experiments. Section 6 explains the contribution and further research issues.

## 2. PROBLEM DEFINITION AND MATHEMATICAL MODEL

This paper considers the fire sequencing problem (FSP) to minimize the total weighted firing completion times of artillery weapons, where the weight of the target represents the threat from the target which may counterattack.

The FSP in this paper considers the following assumptions additionally.

• (1) The targets are assigned to the weapons previously.

• (2) A weapon can fire at most one target at the same time.

• (3) The firing operation of a weapon cannot stop until its completion, thus no preemption is allowed.

• (4) One target can be assigned to multiple weapons. Note that the start time of multiple weapons must be the same, while the end times from weapons may be different.

To formulate the fire sequencing problem, let us present the following notations. There are n targets and m artillery weapons. The firing duration time of weapon j (j = 1, 2, ..., m) to target i (i = 1, 2, ..., n) is denoted by pij. The firing completion time for target i is denoted by Ci. Let wi be the given weight of target i , and if the value wi is high, then it means that the associated target i is more threatening. This paper assumes that if pij = 0 holds, then weapon j doesn’t need to attack target i. Thus only weapon j with pij > 0 need to attack target i.

This paper finds the effective and efficient fire sequencing to minimize the total weighted firing completion time for all the targets. Therefore, the objective function (TC) of this paper is mathematically expressed as $∑ i = 1 n w i C i$.

To present the more detailed explanation on the problem situation, the following example can be considered.

Example 1. There are two targets and three weapons. The required firing duration of each weapon to each target, and the weight information are presented in Table 1, as follows.

There are only two possible fire sequences, such as T1T2 or T2T1 . The makespan value of T1T2 is 13, and the completion times of targets are C1 = 8 , C2 =13 , and the total weighted firing completion time is 55, as shown in Figure 1-(a). On the other hand, if the fire sequencing is T2T1 , then makespan is 14. The completion times are C2 = 6 , C1 =14 , and the total weighted firing completion time is 46, as seen in Figure 1-(b). In this example, although the sequence T2T1 has more longer makespan than T1T2 , we can note that the sequence T2T1 has smaller total weighted completion time value. ■

The fire sequencing problem of this paper can be expressed as the following mixed integer programming. In the mathematical formulation, xi denotes the starttime to attack target i. yik has the value 1 if the attack for target i precedes target k, otherwise 0. W(i, k) denotes the set of common weapons that attacks both the targets i and k.

$min ∑ i = 1 n w i C i$
(1)

subject to

$C i ≥ x i + p i j for all i , j$
(2)

$x i ≥ x k + p k j − M ⋅ y i k , for all j ∈ W ( i , k )$
(3)

$x k ≥ x i + p k i − M ⋅ ( 1 − y i k ) , for all i ∈ W ( i , k )$
(4)

$C i ≥ 0 , x i ≥ 0 , y i k ∈ { 0 , 1 } , for all i , k$

Equation (1) represents the minimization of the total weighted firing completion times, which is the objective cost function in this paper, and Equation (2) represents that the firing completion time for a target is the latest completion time among the assigned weapons. Equations (3) and (4) enforce that if target i precedes target k in the schedule, target k can start its firing only after the completion of target i, and M is an arbitrarily large value.

As discussed earlier, the FSP in this paper is NP-hard, thus as the number of targets and weapons increases, the problem complexity increases. The FSP may be considered in the real-time combat situations, so that the FSP need to be solved via an effective and efficient solution methodologies.

## 3. DOMINANCE PROPERTIES

This paper firstly presents some dominance properties, and may provide the possibility to reduce our search effort to find effective solutions, which can be applied to the algorithms derived in this paper. Let Ω denote the set of the targets having positive firing time from all the weapons, i.e. Ω ={i : pij > 0, 1 ≤ jm}.

Lemma 1. If all the targets are Ω -targets, i.e., all i ∈ Ω, then the optimal firing schedule is that all the targets are sequenced in a non-decreasing order of $max 1 ≤ j ≤ m p i j w i$.

Proof. It can be proved very easily, so the detailed proof is omitted. ■

The following lemma is also presented for two consecutive Ω -targets. Let S be a whole-sequence in which target i immediately precedes target k and $S ˜$ be the same sequence except that the positions of targets i and k are exchanged.

Lemma 2. Consider two consecutive targets i and k , where i and k are Ω -targets, i.e., i, k∈Ω. The sequence S is not worse than the sequence $S ˜$ , if the following relations hold,

• (a) $w k max 1 ≤ j ≤ m p k j ≤ w i max 1 ≤ j ≤ m p i j$

• (b) tm(S) ≤ tm($S ˜$), where target m is positioned right after targets i and k, tm ($S ˜$) and tm($S ˜$) denotes the starting time of target m in the schedule S and $S ˜$ , respectively.

Proof. It can be proved very easily, so the detailed proof is omitted. ■

For two consecutive targets, the following corollary is also presented. W(i) is the set of weapons to fire to target i.

Corollary 1. Consider two consecutive targets i and k, where the assigned weapons are common to targets i and k, i.e., W(i) = W(k). The sequence S is not worse than the sequence $S ˜$ , if the following relations hold,

• (a) $w k max j ∈ W ( i ) p i j ≤ w i max j ∈ W ( k ) p i j$

• (b) tm(S) ≤ tm($S ˜$) .

Proof. It can be proved very easily, so the detailed proof is omitted. ■

Lemma 3. Consider two consecutive targets i and k, such that W(i)⊂W(k). The sequence S is not worse than the sequence $S ˜$, if the following relations hold,

• (a) wk max j∈W(k ) pij ≤ wi max j∈W(i) pkj

• (b) tm(S) ≤tm($S ˜$).

Proof. The completion times , Ci, Ck, $C ˜ k$ and $C ˜ i$ associated with the schedules S and $S ˜$ have the following relation, where tj is the firing completion time of weapon j right before targets i and k :

$w k C ˜ k + w i C ˜ i = w k ( max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j ) + w i ( max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j + max j ∈ W ( i ) p i j ) = w k ( max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j ) + w i ( max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j ) + w i max j ∈ W ( i ) p i j ≥ w k ( max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j ) + w i ( max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j ) + w k max j ∈ W ( k ) p i j = w i ( max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j ) + w k ( max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j + max j ∈ W ( k ) p i j ) ≥ w i ( max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j ) + w k ( max { max j ∈ W ( k ) − W ( i ) t j , max j ∈ W ( k ) t j + max j ∈ W ( k ) p k j } + max j ∈ W ( k ) p i j ) = w i C i + w k C k$

The first inequality holds from the condition (a), and the second inequality holds from the relation W(i)⊂W(k) . Thus it is proved that $w i C i + w k C k ≤ w k C ˜ k + w i C ˜ i$. From the condition (b), the firing completion times for the followingpositioned targets in the schedule S are shorter than $S ˜$ . Accordingly, the sequence S is not worse than the sequence $S ˜$ , under the given conditions.■

Corollary 2. Consider two consecutive targets i and k which have no common weapon, i.e., W(i, k) = φ. It doesn’t matter the sequence between targets i and k.

Proof. It can be proved very easily, so the detailed proof is omitted. ■

## 4. BRANCH-AND-BOUND ALGORITHM

The branch-and-bound algorithm is a solution finding mechanism by an enumeration search of some candidate solutions, which is considered as establishing a rooted tree with some candidates. The procedure explores branches of the tree, which mean subset of the entire solutions. Through exploring the candidate solutions of each node, the node is checked by using upper and lower bounds on optimal solution, and is fathomed if it cannot meet the upper and lower bound condition..

### 4.1. Branching Rule

Each node of the branch-and-bound tree in this paper corresponds to the partial firing sequence. If a node (a partial sequence) is chosen to be branched, then a new target not in the node is selected and attached to the end of the partial sequence associated with the node.

The depth-first search rule is used for the selection of the next node in the branch-and-bound tree. This means that the node with the largest partial sequence can be selected as the next branching node. If a tie occurs, then the node with the lowest lower-bound value is selected as the next node.

### 4.2. Bounding Rule

The bounding rule is used to promote the convergence of the solution based on the upper and lower limits of each node, and the decision is made on whether to search the current node or not. In this paper, the initial upper-bound of the objective function is determined as the heuristic solution value, presented in Section 4.3. Note that UB denotes the heuristic value from heuristic H. If a better feasible solution is obtained in the further B&B (branch-and-bound) procedure, then the upperbound value can updated continuously.

This paper derives the two lower-bound values, and the following notations are used for the derivation.

• π : the partial sequence of targets already decided on the current node.

• nπ : the number of targets included in π .

• Ci (π ) : the firing completion time for target i in π .

• CL(j) (π) : the firing completion time of weapon j in π .

• $π ˜$ : the set of all the targets not included in π .

The objective function $T C ( π ˜ )$ can be expressed as follows, where [k] denotes the k-th positioned target in the entire sequence.

$T C ( π ˜ ) ≥ ∑ i ∈ π ˜ w [ i ] ⋅ { max 1 ≤ j ≤ m C L ( j ) ( π ) + ∑ k = n π + 1 i max 1 ≤ j ≤ m p [ k ] j }$
(5)

The inequality (5) holds because the Ω -jobs are only considered in the set $π ˜$. Inequality (5) can be reexpressed as follows.

$T C ( π ˜ ) ≥ ∑ i ∈ π ˜ ∩ Ω w [ i ] max 1 ≤ j ≤ m C L ( j ) ( π ) + ∑ i ∈ π ˜ ∩ Ω w [ i ] ∑ k = n π + 1 i max 1 ≤ j ≤ m p [ k ] j$
(6)

In the inequality (6), the first term is a constant, and the second term can be minimized by sequencing all the targets in $π ˜$ ∩ Ω in the WPST (weighted shortest processing time) order of $max 1 ≤ j ≤ m p i j w i$ value. If $W S P T ( π ˜ ∩ Ω )$ denotes the weighted total completion times in WSPT order of all the targets in $π ˜ ∩ Ω$, then the first lower-bound LB1 is as follows.

$L B 1 = T C ( π ) + ∑ i ∈ π ˜ ∩ Ω w i max 1 ≤ j ≤ m C L ( j ) ( π ) + W S P T ( π ˜ ∩ Ω )$
(7)

In order to derive the second lower-bound value, the objective function $T C ( π ˜ )$ can be re-expressed as follows.

$T C ( π ˜ ) ≥ ∑ i ∈ π ˜ w [ i ] max 1 ≤ j ≤ m { C L ( j ) ( π ) + ∑ k = n π + 1 i p [ k ] j } ≥ max 1 ≤ j ≤ m { ∑ i ∈ π ˜ w [ i ] C L ( j ) ( π ) + ∑ i ∈ π ˜ w [ i ] ∑ k = n π + 1 i p [ k ] j }$
(8)

In equality (8), the first term is a constant, and the second term can be minimized by sequencing all the targets in $π ˜$ in the WPST order of pij / wi value for weapon j separately. If $W S P T j ( π ˜ )$ denotes the weighted total completion times in WSPT order of all the targets in $π ˜ ∩ Ω$ for each weapon j, then $∑ i ∈ π ˜ w [ i ] ∑ k = n π + 1 i p [ k ] j ≥ W S P T j ( π ˜ )$ holds and the second lower-bound LB2 is as follows.(9)

$L B 2 = T C ( π ) + max 1 ≤ j ≤ m { ∑ i ∈ π ˜ w i C L j ( π ) + W S P T j ( π ) : p i j > 0 }$
(9)

In the branch-and-bound procedure of this paper, the lower-bound LB1 and LB2 are calculated in every node. Among the two values LB1 and LB2, the better lowerbound value is used for the current node as follows.

$L B = max { L B 1 , L B 2 }$
(10)

### 4.3. Construction algorithm

This section proposes a construction (heuristic) algorithm, which provides the initial upper-bound in the branch-and-bound algorithm. The heuristic procedure is very useful, because it can provide the initial solution for the genetic algorithm and the branch-and-bound procedure, and moreover it can provide very efficient and practical construction solutions to the operation manager of the military forces.

The construction algorithm is based on the dispatching scheme similar to the first lower-bound LB1 in section 4.2. Thus the target with the largest $max 1 ≤ j ≤ m p i j w i$ value is assigned more preferentially. The specific procedure of the construction is as follows, where σ denotes the set of all the targets not decided yet at the current step.

Construction algorithm H

• Step 1: If σ is empty, then the algorithm is terminated.

• Step 2: Select target i with the largest $max 1 ≤ j ≤ m p i j w i$ value among the targets in the set σ.

• Step 3: Assign target i, and remove target i from the set σ, and go to Step 1.

## 5. DERIVATION OF GENETIC ALGORITHM

The genetic algorithm (GA) is the most promising meta-heuristic methodology by utilizing the stochastic search intensively. Thus at each generation, the fitness value is evaluated for new generated chromosomes, and more superior chromosomes survive stochastically. Through the crossover or mutation of the selected chromosomes, the new chromosomes are generated, and the excellent ones are preserved for the next generation.

### 5.1. Expression of Genes

The representation of chromosome is very important part to the performance of GA. In this paper, the length of a chromosome corresponds to the number of targets, as shown in Figure 2. Each bit in gene denotes the associated target to be destroyed, thus the bit in represents that the associated target is eliminated in the n-th order.

Example 2. Suppose that there are 7 targets and 3 weapons, as shown in Table 2. The required firing time and weight of each target are also presented in the table. In an example of a chromosome in Figure 3, the firing sequence is 5 → 3 → 1 → 4 → 2 → 7 → 6.

The makespan associated with the chromosome example is 49 seconds. The firing completion time of each target is C5 =8 , C3 =13 , C1 = 21 , C4 = 28 , C2 = 34 , C7 = 40 , C6 = 49 , and the total weighted firing completion times are 16 + 13 + 42 + 112 + 102 + 40 + 147 = 472. ■

### 5.2. Reassignment Procedure

In the process of GA, chromosomes may be generated not to satisfy the assumptions of this paper. Specifically in the operations of crossover, mutation or random generation, some targets may be missing or duplicated inappropriately in generated chromosomes. In this case, the following reassignment procedure should be performed to modify the chromosome.

[Reassignment procedure]

• Step 1: If all targets are assigned properly, then the procedure ends.

• Step 2: Select target k randomly that isn’t included in the chromosome.

• Step 3: Select randomly target m which is duplicated in the chromosome, and select the latest bit among the bits associated with the target m.

• Step 4: Assign target k in the selected bit, and go to Step 1.

The reassignment procedure is a method that assign the missing targets to bits associated with duplicated targets, so that every target occurs only once in a chromosome.

The illustrative example of the reassignment procedure can be shown in Figure 5. In Figure 5, target 1 isn’t included in the gene. The reassignment procedure selects target 3 which occurs in duplication, and selects the latest bit i5 among i2 and i5 , and assigns target 1 to the bit i5 . Therefore the associated chromosome is available because every target occurs only once.Figure 4

### 5.3. Composition of Initial Population and Fitness Calculation

The construction of initial population with promising chromosomes is important for the effectiveness of the overall algorithm. The reason is that the initial population can influence the whole quality of solution procedure. This paper generates 100 chromosomes to the initial population in a random manner.

In the genetic algorithm, the fitness value is usually used for the chromosome selection. If the fitness value is much higher, then the associated chromosome may be more competitive for the next generation. This paper calculates the total weighted firing completion times of each chromosome as the fitness value. Table 1

### 5.4. The Chromosome Selection

In this paper, the roulette wheel selection is used as the chromosome selection procedure to form the next generation, which is very popular technique. The roulette wheel selection follows a stochastic process, so that the chromosome with relatively large fitness value is more likely to be selected for the next generation composition.Table 2

Specifically the selection possibility of a chromosome is assigned with the proportional value of its fitness to the sum of all the fitness values. The width of a chromosome in the roulette wheel is determined as the calculated possibility value. Table 3

### 5.5. Crossover

Crossover produces new chromosomes by using two chromosomes chosen through the roulette wheel selection for the next generation. This paper uses symmetrical 2 point crossover operators, as shown in Figure 6.

To choose the crossover point, the point 1 is selected randomly among the points between the bits in the fronthalf chromosome, and the point 2 is selected symmetrically to the point 1 in the back-half chromosome.

In Figure 6, after determining the crossover points, the fourth bit (4) and (7) are inherited in the same position in the children chromosomes. The bits (6 3 4) in the second parent chromosome are inherited in the positions before point 1 in the first child chromosome, and the bits (1 2 5) in the second parent chromosome are inherited in the positions after point 2 in the first child chromosome, and the second child chromosome can be constructed by a similar manner.

After the crossover operation, the fitness values of the children chromosomes are calculated, which are compared with the fitness values in the existing population. If the child chromosome is better than any chromosome in the existing population, then the old one is replaced with the new one.

### 5.6. Mutation

Mutation modifies a chromosome partially, and then produces a new one. This paper selects a chromosome in the current population by the roulette wheel selection, and chooses randomly a bit in the chromosome, and exchanges the selected bit with any other bit randomly, so that a new chromosome is generated.

This paper also calculates the fitness value of the produced chromosome. By comparing with the existing chromosomes, if the child chromosome is better than any chromosome in the existing population, then the old one is replaced with the new one.

## 6. PERFORMANCE EVALUATION

This section tests the computational performance on the genetic algorithm in Section 3 and the branch-andbound algorithm in Section 4. For the test, the firing duration time values pij (i = 1, ..., n, j = 1, ..., m) are generated from the uniform distribution U[0, 100], where pij have the integer value and may have the value 0. δ denotes the portion of non-zero values out of all pij ’s, and the parameter δ is set to the value 0.6, 0.7, 0.8 and 0.9 in the performance evaluation. The number of targets is chosen from the set {6, 8, 10, 12, 14}, and the number of weapons is chosen from the set {3, 4, 5}. For the performance test, 20 problems are generated for each combination of targets, weapons and the parameter δ , and then totally 1,200 problems are tested. This paper runs iteratively up to 10,000 generations in the genetic algorithm. For each problem instance, the genetic algorithm is performed 10 times, and the average value of ten obtained solution values is used. By referring the study of Kwon et al. (1997), Cha and Kim (2010), the experimental design in this paper is similar to their design. Since their studies were originated from the real military system, the experimental design of this paper may be applicable to the real military system. The algorithms in this paper are coded in C++ Language, and tested in an Intel (R) Core (TM) i3-2120 CPU 3.30GHz, RAM 2.00GB.

The test results are summarized in Tables 3~6. In the table, the average Gap1 (%) is represented by $100 × ( T C H e u − T C O P T ) T C O P T$, and TCHeu and TCOPT denote the feasible solution value generated by the genetic algorithm and the branch-and-bound algorithm, respectively. The average Gap2(%) is represented by $100 × ( T C H e u − L B ) L B$, and LB denotes the lower-bound value derived in Section 3.2. The average computational times of the genetic algorithm and the branch-and-bound algorithm are also presented.

From Table 3~Table 6, it is observed that the performance of the genetic algorithm in average gap gets worse as the value δ approaches to the value 0.8, and the performance gets worse as the numbers of targets and weapons get large. This means that the complexities of the problem instances get larger. The computation time of the branch-and-bound algorithm gets longer up to 355 seconds as the number of targets gets larger, while the genetic algorithm finds efficient solutions within 0.2 seconds averagely. Table 4, 5, 6

For the large number of targets, the algorithm performance is also tested. The values of targets are chosen from the set {20, 25, 30, 35, 40, 45, 50}, and the values of weapons are chosen from the set {3, 4, 5}. 20 problems are also generated for each combination of targets and weapons, and then totally 420 problems are generated. The test results are summarized in Table 7.

In the table, the average Gap2 (%) is only presented. It can be observed from Table 7 that the Gap2 values are between 83% and 178%. Refer that the average Gap2 (%) are up to 130% in Tables 3~6. Although the Gap2 values in Table 7 are relatively large, the values of Gap2 are not much larger than those in Tables 3~6.

## 7. CONCLUSION

This paper considers the fire sequencing problem to minimize the total weighted firing completion time of artillery weapons, and provides effective and efficient solution to the problem. This paper considers the weapon system composed of various types of guns and multiple targets to be destroyed. A genetic algorithm is derived to provide efficient and effective solutions, and a branchand- bound algorithm is also derived to find optimal solutions up to the medium-sized problems. Through the extensive computational tests, the performances of the proposed genetic and the branch-and-bound algorithms are analyzed. The result of research may be extended to the planning for the low altitude anti-ship missile and CIWS (CIWS: Closed in Weapon System) against for plane exploration and shoot-down as well as simultaneous shots situation of the artillery force.

## ACKNOWLEDGMENT

This study was supported by research funds from Dong-A University.

## Figure

The completion times of each fire sequence.

The chromosome structure.

A chromosome example.

Firing sequence of a chromosome example.

An illustrative example of the reassignment procedure.

An example of crossover operation.

## Table

Firing duration and weight information for each target

Firing duration and weight information for each target

Summary of the computational results of the genetic algorithm (δ = 0.6)

Summary of the computational results of the genetic algorithm (δ = 0.7)

Summary of the computational results of the genetic algorithm (δ = 0.8)

Summary of the computational results of the genetic algorithm (δ = 0.9)

The computational results of large number of targets (δ = 0.8)

## REFERENCES

1. R.K. Ahuja , A. Kumar , C.J. Krishna , J.B. Orlin (2007) Exact and heuristic algorithms for the weapontarget assignment problem., Oper. Res., Vol.55 (6) ; pp.1136-1146
2. E. A etin , S.T. Esen (2006) A weapon-target assignment approach to media allocation., Appl. Math. Comput., Vol.175 (2) ; pp.1266-1275
3. Y.H. Cha , Y.D. Kim (2010) Fire scheduling for planned artillery attack operations under timedependent destruction probabilities., Omega, Vol.38 (5) ; pp.383-392
4. J.F. Christ , E.W. Page , G.A. Tagliarini (1993) Performance evaluation of a neural network for weapon-to-target assignment, Proceedings of SPIEthe International Society for Optical Engineering, Orlando, FL, USA, 676-681.,
5. A.R. Eckler , S.A. Burr (1972) Mathematical models of target coverage and missile allocation., Military Operations Research Society,
6. E. Erdem , N.E. Ozdemirel (2003) An evolutionary approach for the target allocation problem., J. Oper. Res. Soc., Vol.54 (9) ; pp.958-969
7. O. Esen , E. A etin , S.T. Esen (2008) A mathematical immunochemoradiotherapy model: A multiobjective approach., Nonlinear Anal. Real World Appl., Vol.9 (2) ; pp.511-517
8. J.A. Hoogeveen , S.L. Van de Velde , B. Veltman (1994) Complexity of scheduling multiprocessor tasks with prespecified processor allocations., Discrete Appl. Math., Vol.55 (3) ; pp.259-272
9. P.A. Hosein , M. Athans (1990) An asymptotic result for the multi-stage weapon-target allocation problem, Proceedings of the 29th Conference onDecision and Control, ; pp.240-245
10. W. Karasakal (2008) Air defense missile-target allocation models for a naval task group., Comput. Oper. Res., Vol.35 (6) ; pp.1759-1770
11. O.J. Kwon , D.H. Kang , K.S. Lee , S.S. Park (1999) Lagrangian relaxation approach to the targeting problem., Nav. Res. Logist., Vol.46 (6) ; pp.640-653
12. O.J. Kwon , K.S. Lee , S.S. Park (1997) Targeting and scheduling problem for field artillery., Comput. Ind. Eng., Vol.33 (3-4) ; pp.693-696
13. Z.J. Lee , W.L. Lee (2003) A hybrid search algorithm of ant colony optimization and genetic algorithmapplied to weapon-target assignment problems., Lect. Notes Comput. Sci., Vol.2690 ; pp.278-285
14. S.P. Lloyd , H.S. Witsenhausen (1986) Weapons allocation is NP-complete, Proceedings of the 1986 Summer Conference on Simulation, ; pp.1054-1058
15. W. P. Malcolm (2004) On the character and complexity of certain defensive resource allocation problems, DSTO-TR-1570, Australian Government Departmentof Defence.,
16. A. Manne (1958) A target assignment problem., Oper. Res., Vol.6 (3) ; pp.346-351
17. S. Matlin (1970) A review of the literature on the missile- allocation problem., Oper. Res., Vol.18 (2) ; pp.334-373