Assigning available resources to fire stations is a main task of fire department\'s administrator in a city. The importance of this problem increases when the number of available resources are inadequate. In this situation, the goal is to assign the limited available resources to fire stations such that the associated penalties of the shortages are minimized. Here, we first give a mathematical approach to consider some penalties for the shortage. Next, we give an integer program to minimize the sum of associated penalties. The proposed model can be used in many other problems arisen from health services, emergency management, and so on. We also propose a heuristic to efficiently solve the problem in a reasonable time. Our proposed heuristic has two phases. In the first phase, using a greedy approach, our proposed heuristic constructs a proper feasible solution. Next, in the second phase, we propose a local search to improve the quality of the solution constructed in the first phase. To show the efficiency of our proposed heuristic, we compare our proposed heuristic with CPLEX based on the running time and the quality of obtained solutions on two groups of problems -real-word problems and randomly generated problems-. The numerical results show that on the 80% of benchmark problems, the obtained solution is the same as CPLEX\'s solutions. Also, the running time of our proposed algorithm is almost 10 times better than CPLEX\'s running time, in average.

Keywords