We focus on the fire scheduling problem (FSP), the problem of determining the sequence of targets to be fired at, for the objective of minimizing makespan to achieve tactical goals. In this paper, we assume that there are m available weapons to fire at n targets (> m) and the weapons are already allocated to targets. One weapon or multiple weapons can fire at one target and these fire operations should start simultaneously while the finish time of them may be different. We develop several dominance properties and a lower bound for the problem, and suggest a branch and bound algorithm implementing them. Also, In addition, heuristic 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. Computational experiments are performed on randomly generated test problems and results show that the suggested algorithm solves problems of a medium size in a reasonable amount of computation time. 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.

In this paper, we consider a two-machine re-entrant permutation flowshop scheduling problem with the objective of minimizing total flowtime, and suggest branch and bound algorithms for the scheduling problem. In this scheduling problem, each job must be p

This paper considers the simultaneously firing model for the artillery operations. The objective of this paper is to find the optimal fire sequence minimizing the final completion time of the firing missions of multiple artillery units for multiple target

In this paper, a best-first branch and bound algorithm based upon the bottom-up approach for the unweighted unconstrained two-dimensional cutting problem is proposed to find the optimal solution to the problem. The algorithm uses simple and effective meth