Complexity of the Fire Sequencing Problem

Abstract

In this note, we introduce the Fire Sequencing Problem, which arises in military operations Given m weapons, n fixed targets and required duration of firing of the weapons on the targets, we want to determine the start time of firing on each target so that makespan is minimized while satisfying various operational constraints. We show that the decision problem of the Fire Sequencing problem is strongly NP-complete and remains strongly NP-complete even if the number of weapons is two. We also briefly discuss the results with respect to the complexities of several well-known scheduling models.