The multi-resource agent bottleneck generalised assignment problem

Özlem Karsu

doi:10.1080/00207543.2010.538745

Return

The multi-resource agent bottleneck generalised assignment problem

2012-01-15

PRE

Özlem Karsu

M. Azizoğlu *

DOI：10.1080/00207543.2010.538745

Original

Original request for help

Save

Abstract

En 中文

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 alpha 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.

Keywords:

bottleneck generalised assignment problem

multi periods

branch and bound algorithm

linear programming relaxation

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.