A Two-Step Tabu Search Heuristic for Multi-Period Multi-Site Assignment Problem with Joint Requirement of Multiple Resource Types

An assignment problem has been extensively studied and applied in many industries. Variations of assignment problem have been proposed and appeared in literatures for many years. This paper extends the variation of assignment problem in the dimension of task and resource by proposing the joint requirement of multiple resource types in a multi-period multi-site assignment problem. The specific characteristic is that there are many multi-skill resource types and tasks require joint requirement of more than one resource type to operate. An application of this model can be found in healthcare industry, especially in clinic networks or hospital networks, which have many service locations, have many resource types such as doctors, nurses or medical equipments and definitely require more than one resource type for operations. This paper proposes a two-step Tabu search heuristic for multi-period multi-site assignment problem with joint requirement of multiple resource types. The specified neighborhood strategy, short-term memory and long-term memory are designed for the addressed problem in order to generate an efficient move to improve solutions. From computational study, solutions from Tabu search algorithm are compared with optimal solutions from CPLEX, and the result shows that, for small size problems, most solutions are close to optimal solutions (average gap = 2.2%), for medium size problems, the algorithm can provide good solutions in a short time comparing with CPLEX (average gap = 5.8%), and for large size problem, four out of five solutions from the proposed algorithm are better than solutions from CPLEX in a limit of time.