A Tabu Search Strategy to Solve Scheduling Problems with Deadlines and Complex Metric Constraints

In this paper a Relaxable Metric Scheduling Problem (RMSP) is defined that extends the classical job shop scheduling problem with the use of complex temporal metric constraints and with the possibility of making the distinction between relaxable and not-relaxable constraints explicit. The paper proposes and experimentally evaluates a tabu search procedure to improve a previously created heuristic solution to the RMSP. The tabu procedure uses the idea of relaxing some temporal constraints to "navigate" the search space and to find a solution. In particular, it tries to produce either a solution where there are no relaxations or a solution where only the constraints classified as relaxable are violated. Experimental results on scheduling problems of increasing size demonstrate the usefulness of the proposed approach.