A Simulated Annealing Algorithm for the Multi Resource Generalized Assignment Problem with Eligibility Constraint

Abstract

The multi-resource generalized assignment problem (MRGAP) is an assignment problem in which each agent has more than one capacity-constrained resource. Although each agent cannot perform each job in real life, in the MRGAP literature it is generally assumed that each job can be assigned to each agent. In addition, working with as few agents as possible can create significant advantages, as each new agent creates audit tracking difficulties and additional costs. For this reason, in this study, the MRGAP problem, in which eligibility constraints are taken into account, has been addressed in a bi-objective manner. The objectives are to minimize the total load squares and the total number of agents. The objective of minimizing the total number of agents has been discussed for the first time in the MRGAP literature. These two objectives considered were scalarized by using the weighted sum method. A simulation annealing algorithm has been developed to solve large-scale problems. Randomly generated test problems were solved with the proposed methods and the obtained results were compared.

Keywords

• generalized assignment problems
• simulated annealing algorithm
• load balancing