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 decisionmaking 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 3060 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 highrisk 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 weaponpower performance, the effectiveness and efficiency of decisionmaking 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 NPhard. Hosein and Athans (1990) have considered a multistage 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 branchandbound 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 multiprocessor 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 NPhard, so that the FSP in this paper is also NPhard. This means that as the number of targets and artillery weapons increases, the problem complexity increases. Since we may face the FSP in the realtime 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 branchandbound 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 p_{ij}. The firing completion time for target i is denoted by C_{i}. Let w_{i} be the given weight of target i , and if the value w_{i} is high, then it means that the associated target i is more threatening. This paper assumes that if p_{ij} = 0 holds, then weapon j doesn’t need to attack target i. Thus only weapon j with p_{ij} > 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 $\sum}_{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 T_{1}T_{2} or T_{2}T_{1} . The makespan value of T_{1}T_{2} is 13, and the completion times of targets are C_{1} = 8 , C_{2} =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 T_{2}T_{1} , then makespan is 14. The completion times are C_{2} = 6 , C_{1} =14 , and the total weighted firing completion time is 46, as seen in Figure 1(b). In this example, although the sequence T_{2}T_{1} has more longer makespan than T_{1}T_{2} , we can note that the sequence T_{2}T_{1} 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, x_{i} denotes the starttime to attack target i. y_{ik} 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.
subject to
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 NPhard, thus as the number of targets and weapons increases, the problem complexity increases. The FSP may be considered in the realtime 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 : p_{ij} > 0, 1 ≤ j ≤ m}.
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 nondecreasing order of $\frac{{\text{max}}_{1\le j\le m}{p}_{ij}}{{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 wholesequence in which target i immediately precedes target k and $\tilde{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 $\tilde{S}$ , if the following relations hold,

(a) ${w}_{k}\hspace{0.17em}{\text{max}}_{1\le j\le m}\hspace{0.17em}{p}_{kj}\le {w}_{i}\hspace{0.17em}{\text{max}}_{1\le j\le m}{p}_{ij}$

(b) tm(S) ≤ tm($\tilde{S}$), where target m is positioned right after targets i and k, t_{m} ($\tilde{S}$) and tm($\tilde{S}$) denotes the starting time of target m in the schedule S and $\tilde{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 $\tilde{S}$ , if the following relations hold,

(a) ${w}_{k}\hspace{0.17em}{\text{max}}_{j\in W\left(i\right)}\hspace{0.17em}{p}_{ij}\le {w}_{i}\hspace{0.17em}{\text{max}}_{j\in W\left(k\right)}{p}_{ij}$

(b) t_{m}(S) ≤ t_{m}($\tilde{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 $\tilde{S}$, if the following relations hold,
Proof. The completion times , C_{i}, C_{k}, ${\tilde{C}}_{k}$ and ${\tilde{C}}_{i}$ associated with the schedules S and $\tilde{S}$ have the following relation, where t_{j} is the firing completion time of weapon j right before targets i and 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}\le {w}_{k}{\tilde{C}}_{k}+{w}_{i}{\tilde{C}}_{i}$. From the condition (b), the firing completion times for the followingpositioned targets in the schedule S are shorter than $\tilde{S}$ . Accordingly, the sequence S is not worse than the sequence $\tilde{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. BRANCHANDBOUND ALGORITHM
The branchandbound 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 branchandbound 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 depthfirst search rule is used for the selection of the next node in the branchandbound 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 lowerbound 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 upperbound 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 (branchandbound) procedure, then the upperbound value can updated continuously.
This paper derives the two lowerbound 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 π .

C_{L}(j) (π) : the firing completion time of weapon j in π .

$\tilde{\pi}$ : the set of all the targets not included in π .
The objective function $TC\left(\tilde{\pi}\right)$ can be expressed as follows, where [k] denotes the kth positioned target in the entire sequence.
The inequality (5) holds because the Ω jobs are only considered in the set $\tilde{\pi}$. Inequality (5) can be reexpressed as follows.
In the inequality (6), the first term is a constant, and the second term can be minimized by sequencing all the targets in $\tilde{\pi}$ ∩ Ω in the WPST (weighted shortest processing time) order of $\raisebox{1ex}{${\text{max}}_{1\le j\le m}{p}_{ij}$}\!\left/ \!\raisebox{1ex}{${w}_{i}$}\right.$ value. If $WSPT\left(\tilde{\pi}\cap \Omega \right)$ denotes the weighted total completion times in WSPT order of all the targets in $\tilde{\pi}\cap \Omega $, then the first lowerbound LB_{1} is as follows.
In order to derive the second lowerbound value, the objective function $TC\left(\tilde{\pi}\right)$ can be reexpressed as follows.
In equality (8), the first term is a constant, and the second term can be minimized by sequencing all the targets in $\tilde{\pi}$ in the WPST order of p_{ij} / w_{i} value for weapon j separately. If $WSP{T}_{j}\left(\tilde{\pi}\right)$ denotes the weighted total completion times in WSPT order of all the targets in $\tilde{\pi}\cap \Omega $ for each weapon j, then $\sum _{i\in \tilde{\pi}}{w}_{\left[i\right]}{\displaystyle \sum _{k={n}_{\pi}+1}^{i}{p}_{\left[k\right]j}}\ge}\hspace{0.17em}WSP{T}_{j}\left(\tilde{\pi}\right)$ holds and the second lowerbound LB_{2} is as follows.(9)
In the branchandbound procedure of this paper, the lowerbound LB_{1} and LB_{2} are calculated in every node. Among the two values LB_{1} and LB_{2}, the better lowerbound value is used for the current node as follows.
4.3. Construction algorithm
This section proposes a construction (heuristic) algorithm, which provides the initial upperbound in the branchandbound algorithm. The heuristic procedure is very useful, because it can provide the initial solution for the genetic algorithm and the branchandbound 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 lowerbound LB_{1} in section 4.2. Thus the target with the largest ${\text{max}}_{1\le j\le m}\raisebox{1ex}{${p}_{ij}$}\!\left/ \!\raisebox{1ex}{${w}_{i}$}\right.$ 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 ${\text{max}}_{1\le j\le m}\raisebox{1ex}{${p}_{ij}$}\!\left/ \!\raisebox{1ex}{${w}_{i}$}\right.$ 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 metaheuristic 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 nth 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 C_{5} =8 , C_{3} =13 , C_{1} = 21 , C_{4} = 28 , C_{2} = 34 , C_{7} = 40 , C_{6} = 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 i_{5} among i_{2} and i_{5} , and assigns target 1 to the bit i_{5} . 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 backhalf 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 branchandbound algorithm in Section 4. For the test, the firing duration time values p_{ij} (i = 1, ..., n, j = 1, ..., m) are generated from the uniform distribution U[0, 100], where p_{ij} have the integer value and may have the value 0. δ denotes the portion of nonzero values out of all p_{ij} ’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) i_{3}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\times \frac{\left(T{C}_{Heu}T{C}_{OPT}\right)}{T{C}_{OPT}}$, and TC_{Heu} and TC_{OPT} denote the feasible solution value generated by the genetic algorithm and the branchandbound algorithm, respectively. The average Gap2(%) is represented by $100\times \frac{\left(T{C}_{Heu}LB\right)}{LB}$, and LB denotes the lowerbound value derived in Section 3.2. The average computational times of the genetic algorithm and the branchandbound 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 branchandbound 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 mediumsized problems. Through the extensive computational tests, the performances of the proposed genetic and the branchandbound algorithms are analyzed. The result of research may be extended to the planning for the low altitude antiship missile and CIWS (CIWS: Closed in Weapon System) against for plane exploration and shootdown as well as simultaneous shots situation of the artillery force.