1.Introduction

This research considers the issue of scheduling enemy targets which are assigned to different artillery units under the situation of planned artillery attack operations. In the planned artillery attack operation, it is assumed that information on a group of enemy targets such as the locations and characteristics is already on hand and the operation plan will be prepared in advance before the execution of operation. In combat situation, identified enemy targets should be fired and destroyed by various friendly fire power such as combat aircrafts, field artillery units, and missiles, etc. In this research, among these fire power assets, we mainly focus on the field artillery units. A planned artillery attack operation is executed with two sequential procedures. First, at assignment phase, enemy targets are assigned to a weapon or a group of weapons. Here, a weapon represents an artillery battery, which is the basic unit to execute artillery attack operations and is typically composed of six howitzers. Note that when there are more targets than available weapons, one weapon may have to be assigned to more than one target. Second, at scheduling phase, scheduling firing operations against the targets that are assigned to each weapon is calculated. Note that a target can be assigned to more than one weapon and the prespecified set of weapons should start firing at the target simultaneously to achieve surprise effect. In this paper, we assume that the assignment is given, thus we only consider the second phase which is called fire scheduling problem (FSP).

In the following, we will explain that the FSP is the generalization of multiprocessor task scheduling problem (MTSP). In MTSP, a collection of n tasks has to be executed by m processors. Task J_j (j = 1, …, n) requires processing during a given uninterrupted time p_j [13]. Each task requires the simultaneous use of a set of pre-specified processors for its execution; each processor can execute at most one task at a time. Note that, in FSP the processing time of each target (task) may be different among prespecified weapons (processors) due to the assignment results. Thus, the FSP is a generalized version of the MTSP.

Since most research on the weapon management is mainly focused on the quality of weapon firing [1, 2, 25], the research on the FSP is very rare. First introduced the FSP, Kwon et al. [22] consider the FSP with the objective of minimizing makespan under the assumption that the targets are fixed (do not move). Note that they focus on achieving surprise attack effect through the quickest completion of the firing operation. Kim and Lee [19] also consider the FSP and they provide a heuristic algorithm. Kim and Lee [18] combined the fire target allocation problem and sequencing problem in one algorithm and suggest a heuristic approach.

Due to the lack of literature on the FSP, we mainly review the multiprocessor task scheduling problem which is different but share common characteristics comparing with traditional machine scheduling theory. Bozoki et al. [6] first considered the multiprocessor task scheduling problem. However, the research area did not attract much attention until the computing power tremendously increases in 1990’s. Along with survey papers by Drozdowski [12] and Lee et al. [25], there have been a number of research articles on the multiprocessor task scheduling problems. Bozoki et al. [6], Bianco et al. [4] and Kramer [20] provide branch and bound algorithms for the problem.

The multiprocessor task scheduling problem is denoted as Pk|fix|Cmax in the literature [14]. Feasibility and approximability of the Pk|fix|Cmax problem have been studied by many researchers. The P2|fix|Cmax problem is a generalized version of the classical job scheduling problem on a 2-processor system [13], thus it is NP-hard. Kubale [21] studied the complexity of the particular problem of scheduling tasks that require at most two prespecified processors. Chen et al. [9] developed a fully polynomial time approximation scheme for the P2|fix|Cmax problem. Hoogeveen et al. [15] showed that the P3|fix|Cmax problem is NP-hard in the strong sense thus it does not have a fully polynomial time approximation scheme unless P = NP. Note that firing scheduling problem is also NP-hard since FSP is generalized version of P3|fix| Cmax problem. Blazewicz et al. [5] developed a polynomial time approximation algorithm of ratio 4/3 for the problem P3|fix|Cmax, which was improved by Dell’Olmo et al. [11], who gave a polynomial time approximation algorithm of ratio 5/4 for the same problem. Both algorithms are based on the study of a special type of scheduling called normal scheduling. Brucker et al. [7] present polynomial algorithms for multiprocessor task problems with unit processing times and more general objective functions. More recently, Amoura et al. developed a polynomial time approximation scheme for the problem Pk|fix|Cmax for every fixed integer k. Polynomial time approximation schemes for a more generalized version of the Pk|fix|Cmax problem have also been developed recently [10, 17]. Huang et al. [16] derive an approximation algorithm of ratio 1.5 for the P4|fix|Cmax problem, which significantly improves the best previous ratio of 2 for practical algorithms for the problem. Recently, Yoon et al. [26] use the basic concept of a branch-and-bound algorithm to find the optimal fire sequence minimizing the completion time of firing operations and Cha and Kim [8] propose the branch-and-bound algorithm for minimizing the threat rate during the firing operation. In this research, we extend the problem described by Yoon et al. [26] and develop several dominance properties and a lower bound for the FSP and present a branch and bound (B&B) algorithm using them. Due to the complexity of the problem and the requirement of prompt decisions in practice, we also suggest heuristic algorithms that can give reasonably good solutions in a short time. The heuristic algorithms are also used in the B&B algorithm for an initial upper bound. This paper is organized as follows. In section 2, we describe the FSP considered in this study in more detail. Sections 3 and 4 present dominance properties and the branch and bound algorithm, respectively. For evaluation of the performance of the suggested algorithms, a series of computational tests is performed on randomly generated problem instances and results are reported in section 5. Finally, section 6 concludes the paper with a short summary and recommendations for further research.

2.Problem Description

The fire scheduling problem (FSP) considered in this research is the problem of scheduling a set of targets for the objective of minimizing makespan. To describe the branch and bound algorithm clearly, we first define terms that will be used in this research.

Note a job for a single-weapon target, which is assigned to only one weapon, is composed of only one firing operation, while a job for a multiple-weapon target, which is assigned to more than one weapon, is composed of two or more firing operations. In this research, a pair (i, j) represents a firing operation in which weapon i is assigned to target j. For example, if weapon 1, 2, and 4 are assigned to a target 1, then job 1 (or target 1) is composed of three firing operations (1, 1), (2, 1) and (4, 1).

In this study, the following assumptions are made.

Solution representation scheme

Schedules are represented with a sequence of jobs. On each weapon, a firing operation of a job in an earlier position of the sequence is scheduled earlier. If two targets require firing operations that are assigned to two disjoint sets of weapons, we only consider a sequence in which the job with an operation assigned to the lowest-indexed weapon is placed earlier.

While there may be various solution representation schemes for this problem, we represent the schedules (partial schedules) with a sequence of jobs. This implies that the sequence of jobs determine a unique schedule. Remind that a job is set of firing operations against one target. On each weapon, a firing operation of a job in an earlier position of the sequence is scheduled earlier than that of a job placed in a later position. In other words, the sequence of firing operations on each weapon is obtained from the sequence of jobs. Note that a job in an earlier position in the sequence is not necessarily started earlier than another job if the two jobs are compatible. When a schedule is constructed from a sequence, one should consider the constraint that firing operations of the same job should be started simultaneously.

In the following we present a mathematical formulation of the FSP. In the formulation the following notation is used and the other notation follows the same with previous definition.

i index for weapon systems (i = 1, …, W)

j index for targets (j = 1, …, T)

W(j, k) set of weapons that are needed for firing at both targets j and k

x_jk binary variable that is equal to 1 if firing operation for target j precedes that for target k in a given firing sequence, for all j, k∈R, j < k

M a large number

Now, a nonlinear integer programming formulation is given.

Minimize C_max

Subject to

Equation (2) and (3) are the disjunctive constraints which represent the starting time relationship between any two targets. x_jk is a binary variable which indicates whether task j precedes task k in the sequence and M is a large number. Note that if x_jk = 1, then the start of job k, t_k ≥ t_j+max (d_ij) and equation (2) becomes nonbinding because the right hand side becomes a large number. If x_jk = 0, then the start of job j, t_j ≥ t_k+max (d_ik) and equation (3) becomes nonbinding. It is possible that several targets can be fired at simultaneously if they do not share a common weapon that is supposed to fire at them. If W(j, k) is empty, then max(d_ij) and max (d_ik) will be 0 and, by constraints (2) and (3), t_j = t_k can be accomplished.

For a better description of the problem we present a simple example in which a schedule is represented by a sequence of jobs. For example, in <Figure 1>, three jobs (T1, T2, and T3) are scheduled on three weapons. T1 and T3 represent set of firing operations against multiple-weapon targets 1 and 3, respectively, while T2 represents a firing operation against a single-weapon target 2. A job sequence (1-2-3) represents the schedule as shown in the figure. With this solution representation method, one can always generate a unique nondelay schedule from a sequence of the jobs.

3.Dominance Properties

In this section, we present dominance properties that can be used in a branch and bound (B&B) algorithm for the fire scheduling problem (FSP) considered in this research. We use the following additional notation.

W(j) set of weapons which are assigned to target j

W(j, k) set of weapons which are assigned to both target j and k

d_ij firing duration from weapon i to target j

TS_jk saving period when target k is immediately sequenced after target j

σ partial sequence

σ_jk partial sequence appending job j and k in this order at partial sequence σ

w_jk weapon which decides the completion time of partial sequence σ_jk

In the notation, TS_jk means the saving period [19] when target j and k are scheduled in this order. Clearly, that implies value of (sum of longest firing duration of target j and that of target k)-(the firing duration needed when target j and k are combined). In <Figure 2>, longest firing duration of target j is 4 and that of target k is 3. If target j and k are sequenced as shown in the figure, the firing duration of combined targets j and k is 5. Thus, the saving period of this example is 2 (4+3-5). Obviously, the TS_kj which is the saving period of combined target of target k first and j second is 0. Also, the saving period is calculated with the formulation as in notation. That is max_iÎW(j) (d_ij) is 4, max_iÎW(j,k) (d_ij) is 2, and max_iÎW(k)(d_ik) is 3. Thus TS_jk is equivalent to min{4-2, 3}.

Now, we present an optimal solution property of twoweapon problem in which there are two weapons.

Proposition 1Consider two targets in two-weapon problem : a two-weapon target j and single-weapon target k. IfT S jk = max d ij i ∈ W j − max d ij = j ∈ W j , k max d ik iis satisfied, then in an optimal solution of the problem, target k is immediately sequenced after target j.

Proof : Suppose there are two single-weapon targets k and k’ which are assigned to weapon i. Let S be a sequence that satisfy the sequencing rule, and S’ be a sequence that is identical to S except that the position’s of targets k and k’ are interchanged. We will show that the makespan of the sequence S is at least equal to that of the sequence S’. We consider two cases related to the durations of two targets : (Case 1) d_ik < d_ik’ and (Case 2) d_ik > d_ik’.

(Case 1) Note that, TS_jk = TS_jk’ and comparing to the contribution of the targets j and k to the makespan in sequence S, that of targets j and k’ in sequence S’ increases by the difference of two durations (d_ik-d_ik’). In addition, if the makespan of sequence S’ is determined by weapon i, then there is no makespan difference between sequence S and S’. However, if the makespan of sequence S’ is determined by the other weapon, then makespan of S’ is increased by (d_ik’-d_ik).

(Case 2) Note that, TS_jk > TS_jk’ due to d_ik > d_ik’ and the contribution of the targets j and k to the makespan in sequence S is equal to that of targets j and k’ in sequence S’. In addition, if the makespan of sequence S’ is determined by weapon i, then makespan of S’ is increased by (d_ik-d_ik’). However, if the makespan of sequence S’ is determined by the other weapon, then there is no makespan difference between sequence S and S’. This completes the proof. ■

The following proposition gives a dominance property related to a target which is supposed to be appended in partial sequence σ.

Proposition 2 Considering partial sequence σ, if an unscheduled target j can be inserted idle times between two sequenced targets (implying that the target j can be positioned at earlier period than the time according to the schedule representation scheme) without changing other sequenced targets’ schedule, then the current partial solution is dominated.

Proof : Consider a sequence, S, in which job k is scheduled at t_k. according to the schedule representation scheme. Consider a sequence, S’, that is identical to S except that the job k is inserted between two sequenced jobs (positioned earlier period). We will prove this proposition by showing that the completion time of sequences oriented from sequence S’ is at least as good as that of sequences oriented from sequence S. Observe that sequences originated from S can be exactly replicated with sequences originated from S’ except job k. Furthermore, after insertion of job j at earlier position, the completion time of sequences originated from S’ may be decreased. ■

This dominance condition can be applied when an unscheduled job can be inserted idle times between two sequenced targets of partial sequence σ. If there exists such an unscheduled job, then σ can be deleted from further consideration in the B&B algorithm.

Proposition 3Consider two unscheduled targets, targets j and k. Assume that they are incompatible, TS_jk>TS_kj, and firing start time of target j of σ_jk is same as that of k of σ_kj. If all unscheduled targets except target j and k are assigned to weapon w_kj, then σ_jk dominates σ_kj.

Proof : Since TS_jk > TS_kj, the latest completion time of σ_jk is strictly less than that of σ_kj. In any schedule generated from partial schedule σ_kj, if the weapon w_kj is commonly assigned to all unscheduled targets, then the earliest start time of any unscheduled targets is the latest completion time of partial schedule σ_kj. However, in any schedule generated from partial schedule σ_jk, the earliest start time of any unscheduled targets is the completion time of σ_jk which is less than that of σ_kj. Thus, σ_jkdominatesσ_kj. ■

This dominance condition can be applied when the target (or job) k is placed at the last position of the current partial sequence, σ. If there is another target j not in σ which is incompatible with the target k and target j and k satisfy the conditions in the proposition 2.2, then a sequence composed of σ followed by the target j can be deleted from further consideration in the B&B algorithm. The following proposition is applied when two unsequenced targets are assigned to all weapons.

4.Branch and Bound Algorithm

In the branch and bound (B&B) algorithm described next, each node of the tree corresponds to a sub-problem, which is defined by a partial sequence of jobs. We call the set of jobs not included in partial sequence as un-sequenced jobs. At the beginning of the B&B algorithm (root node), there is an empty sequence of jobs and when the algorithm terminates we gain a complete sequence of jobs such that the latest completion time is minimized. a node at level l in the branching tree represents a partial sequence in which l jobs are scheduled. At level 1, n nodes are created, which n is the number of jobs. For each node in this level, a specific job is sequenced to the 1^st position in the partial sequence. At level 2, n(n-1) nodes are created. This means that for each level 1 node there are (n-1) un-sequenced jobs. In this way, the lower level nodes are generated and the maximum number of possible nodes is n+n(n-1)+n(n-1)(n-2)+…+ n(n-1) (n-2)…(2). According to the solution representation scheme used in this study, the B&B tree is constructed in detail as follows. A job included in a partial sequence corresponding to a node closer to the root node are placed in an earlier position in the sequence than those corresponding to its child nodes farther from the root node. The selection of a node to branch from follows the depth first rule, which is a node with the most jobs included in the associated partial sequence is selected for branching. In case of ties, a node with the minimum lower bound is selected. When a node is branched, one or more nodes are generated by appending one more job at the end of the partial sequence associated with the node being branched. When child nodes are generated from a selected parent node, we check redundancy of (partial) sequences as described in the solution representation scheme.

That is, if two targets are compatible, we only consider a sequence in which the job with an operation assigned to the lowest-indexed weapon is placed earlier. If a node is related with a sequence that does not satisfy this rule, the node is deleted from consideration (pruned) in the B&B procedure. When a node is generated, the dominance conditions presented earlier are checked, and nodes corresponding to dominated sequences are also pruned. For each child node that is not pruned, a lower bound on the makespan is calculated. A node is fathomed if its lower bound is greater than the current incumbent solution.

Upper bound (Heuristic-H)

To create a sequence in the branch and bound (B&B) algorithm, four local search algorithms are suggested in this study. In these algorithms, we construct initial solution with NEH algorithm proposed by Nawaz et al. [24], and a set of neighborhood solutions are explored for the current solution and the best neighborhood solution is selected as the new current solution. To explore neighborhood solutions (sequences) from the current solution, we use two methods, insertion and interchange. The insertion method starts by selecting a job in the current sequence and inserting this job into all possible positions in the sequence. On the other hand, the interchange method starts by selecting a job in the current sequence and exchanging its position with each of all other jobs in the sequence. We employed four local search algorithms associated with insertion and interchange: IS, IC, ISIC, and ICIS. The IS and IC algorithm generate neighborhood solutions with insertion and interchange method, respectively. The ISIC and ICIS algorithms in which IS and IC are executed sequentially and IC and IS are executed sequentially, respectively. Since it is expected to take very short time to solve a problem with the heuristic algorithm, we execute both of ICIS and ISIC and select the better solution as the initial upper bound in our B&B algorithm.

A lower bound

A lower bound is obtained for each node that cannot be eliminated by the dominance properties. The lower bound associated with partial sequence σ is maximum value of summing, for each weapon, (1) completion time of sequenced jobs in σ and (2) total duration of each firing operation of un-sequenced jobs (jobs not included in partial sequence σ). The lower bound is computed as

where c_i is the completion time of weapon i with partial sequence σ and U is the set of un-sequenced targets. The sum of durations of un-sequenced jobs can be regarded as the minimum total firing duration of un-sequenced jobs.

5.Computational Experiments

First, to test the performance of the proposed algorithm, we use the branch-and-bound algorithm built in ILOG CPLEX 11.0. For the test, we generated 75 problems, 5 problems for each of all combination of one level for the number of weapon (2), 5 levels for the number of targets (from 10 to 14), three levels for the percentage of single-weapon target among all targets (20%, 50%, and 80%). All tests were performed on a personal computer with a Intel® Core™ i5 CPU at 3.2GHz clock speed.

Results of the test are given in <Table 1>, which shows the average computational time and number of problems that were not solved to the optimality in time limit. As can be seen from the table, the B&B algorithm performs better than CPLEX with respect to both CPUT and NPNS. Thus, we can conclude that ILOG CPLEX takes much more computational time to solve a problem than the suggested B&B algorithm.

Before evaluating the performance of the B&B algorithm, we test the effectiveness of the dominance properties, the lower bound, and the heuristic algorithm used in the B&B algorithm. For this test, we compare four B&B algorithms : BB with all of these included; BB-DP, the B&B algorithm without dominance properties, i.e., the one with the lower bound and the heuristic algorithm only; BB-LB, the one without the lower bound; and BB-H, the one without the heuristic algorithm. Since it takes very short time to solve a problem with the heuristic algorithm, we execute both of ICIS and ISIC and select the better solution as the initial upper bound in our B&B algorithm. It was tested on 30 randomly generated test problems, 5 problems for each of all combinations of two levels for the number of weapons (3 and 6), three levels for the number of targets (10, 12, and 14). The number of weapons needed for a target was generated from the uniform distribution with range [40%, 80%] of weapon number and rounded down for the integrality. The assigned number of targets to each weapon is balanced among different weapons. The durations (d_ij) of the firing operations against targets were generated from the discrete uniform distribution with rang [2, 4]. The execution time for each problem was limited to 3,600 seconds.

Results of the test are shown in <Table 2>, which shows the average CPU time, the number of problems that were not solved to the optimality in 3600 seconds, and the average ratio of the numbers of nodes generated to that of nodes that would have been generated if none of the dominance properties, the lower bound and the heuristic algorithm had been used in the B&B algorithm. If the algorithm could not solve a problem within 3,600 seconds, we calculate the CPU time of the problem as 3,600 seconds. For a better exposition of the results, we prepared another table, <Table 3>, which shows the ratios of the CPU times and the ratios of the numbers of nodes generated in the B&B procedures. The lower bound was more effective than the dominance properties and the heuristic in reducing the computation time as well as in fathoming nodes in the B&B algorithm. However, use of the dominance properties and the heuristic algorithm reduced the CPU time although the reduction was not very impressive. This means that the benefit of using these, i.e., pruning dominated partial solutions, exceeds the cost of using them, i.e., the time required for checking the dominance conditions or for obtaining a good initial upper bound. In the following, we further test BB, the B&B algorithm with the dominance properties and heuristic algorithm as well as the lower bound.

For this main test, 60 problems were additionally generated, 5 problems for each of all combination of three levels for the number of weapons (3, 6, and 9), four levels for the number of targets (16, 18, 20, and 22). As in the previous test, the upper limit of 3600 seconds is given for each problem. Results of the test are given in <Table 4>. The table shows the average CPU time and the number of problems which were not solved to the optimality within the time limit as well as average percentage gap of the heuristic solutions from the BB solutions and the number of problems the heuristic algorithm gave the same solutions with BB solutions.

The B&B algorithm solved to the optimality 42 problems out of 60 within 3,600 seconds. The CPU time was affected more by the number of weapons than the number of targets. This may be because, if there are more weapons (when the number of target is given), the weapon-target allocation graph becomes sparse in general. This results in weaker lower bound and takes longer time when the number of weapons is larger. The heuristic algorithm worked relatively well. In 20 problems it gave the same solutions as those obtained from the B&B algorithm, and the overall average percentage gap of the heuristic solution (from the solutions of BB) was 5.10%.

6.Summary

This research considered the problem of scheduling fire operations with the objective of minimizing makespan. Several dominance properties and a lower bound on the latest completion time for a partial schedule were found and used to develop a branch and bound algorithm. In addition, heu ristic algorithms that can be used for obtaining an initial upper bound in the B&B algorithm and for obtaining good solutions in a short time were developed. The proposed lower bound, the dominance properties, and the heuristics for upper bound are tested in B&B respectively, and the result showed that lower bound is effective to fathoming nodes and the dominance properties and heuristics also worked well. Also, it is showed that the CPU time required by this algorithm increases rapidly as the problem size increases. Therefore, the suggested B&B algorithm would be limited to solve large size problems. However, the employed heuristic algorithms can be effectively used in the B&B algorithm and can give good solutions for large problems within a few seconds.