Solving multiple capacitated scheduling problems with Tabu Search

This work concerns a tabu search algorithm to solve instances of the Multiple Capacitated Job-Shop Scheduling Problem (MCJSSP). MCJSSP extends the classical Job-Shop Scheduling Problem (JSSP) with the use of resources with integer capacity greater than one. We propose and experimentally evaluate a procedure to improve the makespan bf a MCJSSP's solution created with a heuristic method. The work proposes a basic tabu search algorithm which uses two types of moves: vertical and horizontal. This basic strategy is integrated in a meta strategy called Tabu Search with Back Jump Tracking [2]. The local search procedure has been tested on a set of multiple capacitated scheduling problems and the solutions' makespans are comparable with the best results available in literature for the previous set of problems.