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.

  This paper deals with the problem of scheduling jobs and rate-modifying activities on parallel machines. A rate-modifying activity is an activity that changes the production rate of equipment such as maintenance and readjustment. If a job is scheduled a

  In this paper, we study flowshop scheduling problems with availability constraints. In such problems, n jobs have to be scheduled on m machines sequentially under assumption that the machines are unavailable during some periods of planning horizon. The

This paper deals with the problem of scheduling jobs and rate-modifying activities on parallel machines, motivated by a problem commonly found in the surface-mount technology of electronic assembly lines. A rate-modifying activity involving repair, maintenance and readjust is an activity that changes the production rate of equipment under consideration. In this paper, the processing time of a job scheduled before the activity is equal in each parallel machines. On the other hand, if the job is scheduled after the rate-modifying activity than the process time depends on the modifying rate of the activity. Our purpose is to schedule the rate-modifying activities and jobs to minimize the makespan on parallel machines which is NP-hard. We propose a branch and bound algorithm to solve medium size problems optimally. Also we develop three heuristics, Modified Longest Processing Time (MLPT), MULTIFIT and COMBINE algorithms to solve large size problems.