The multi-resource agent bottleneck generalised assignment problem

摘要

In this study, we consider the multi resource agent bottleneck generalised assignment problem. Our aim is to minimise the maximum load over all agents. We take our motivation from an assignment problem faced in heating, ventilating and air conditioning sector. We study the linear programming (LP) relaxation of the problem. We use the optimal LP relaxation solutions in our branch and bound algorithm while defining bounding and branching schemes. We find that our branch and bound algorithm returns optimal solutions to the problems with up to 60 jobs when the number of agents is 5, and up to 30 jobs when the number of agents is 10, in less than 20 minutes. To find approximate solutions, we define a tabu search algorithm and a approximation algorithm. Our computational results have revealed that both algorithms can find high quality solutions to large sized instances very quickly. To the best of our knowledge our study is the first reported attempt to solve the problem. We hope our study fills an important gap in the literature.