A limited resource assignment problemwith shortage in the re department

Assigning available resources to re stations is a main task of re depart ment s administrator in a city. The importance of this problem increaseswhen the number of available resources are inadequate. In this situation,the goal is to assign the limited available resources to re stations such thatthe associated penalties of the shortages are minimized. Here, we rst givea mathematical approach to consider some penalties for the shortage. Next,we give an integer program to minimize the sum of associated penalties. Theproposed model can be used in many other problems arisen from health ser-vices, emergency management, and so on. We also propose a heuristic toefficiently solve the problem in a reasonable time. Our proposed heuristichas two phases. In the rst phase, using a greedy approach, our proposedheuristic constructs a proper feasible solution. Next, in the second phase, wepropose a local search to improve the quality of the solution constructed inthe rst phase. To show the efficiency of our proposed heuristic, we com-pare our proposed heuristic with CPLEX based on the running time and thequality of obtained solutions on two groups of problems (real-word problemsand randomly generated problems). The numerical results show that on the80% of benchmark problems, the obtained solution is the same as CPLEX ssolutions. Also, the running time of our proposed algorithm is almost 10times better than CPLEX s running time, in average

کلیدواژه ها:

Resource assignment problem ، Fire stations ، Shortage ، Integer programming ، Heuristics