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

Abstract

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. This specific characteristic is that there are many multi-skill resource types and tasks require joint requirement of more than one resource type for operation. 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 to suitable for the problem and to produce an efficient move to better 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, for medium size problems, the algorithm can provide good solutions in a short time comparing with CPLEX, 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.