A Modified Tabu Thresholding Approach for the Generalised Restricted Vertex Colouring Problem

We present a modification of the Tabu Thresholding (TT) approach and apply it to the solution of the generalised restricted vertex colouring problem. Both the bounded and unbounded cases are treated. In our algorithms, the basic TT elements are supplemented with an evaluation function that depends on the best solution obtained so far, together with a mechanism which reinforces the aggressive search in the improving phase, and new diversification strategies which depend on the state of the search. The procedure is illustrated through the solution of the problem of minimising the number of workers in a heterogeneous workforce.