In fire fighting, time and effort required to control a fire increase if the beginning of the fire containment effort is delayed. The problem of scheduling a single fire fighting resource when there are N ≥ 2 fires to be controlled may be tackled using the concept of deteriorating jobs for the time needed for fire suppression. This paper considers the problem in the case where set-up times are incorporated. The objective is to maximize the total value of the burnt areas remaining after the completion of the containment operation. A branch and bound algorithm is presented, using heuristic algorithms to obtain the upper bound and an initial lower bound. A dominance rule is also applied to reduce the time required for exploring the solution space.