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. This research proposes a multi-period multi-site assignment problem with joint requirement of multiple resource types. In this problem, there are many multi-skill resource types, and each task requires joint of more than one resource type to operate. The decisions in the proposed model are not only assigning resources to tasks as in classic assignment problems but also allocating resources to sites in each period. An integer linear programming model and a heuristic approach based on Tabu search algorithm (Two–step Tabu search heuristic) are developed. 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. In addition, the surrogate objective is introduced to evaluate the quality of neighborhoods, and only good neighborhoods are considered to increase search speed. The quality of solutions from the developed heuristic are compared with optimal solutions from CPLEX. For small size problems, the result shows that the proposed heuristic can find solutions close to optimum in most problems at the average optimal gap of 0.09%. For medium size problems, the algorithm can provide good solutions in a reasonable time at the average optimal gap of 4.42%. Finally, for large size problems whose computational time of CPLEX is limited to 10 hours, the average gap between solutions from heuristic and upper bounds from CPLEX is 8.28%.