A tabu seach approach to machine scheduling

In this paper we apply the tabu search (TS) technique to a complex machine scheduling problem. The problem can be considered as a generalization of the job-shop problem with both simple and parallel machines, job batches, setup times and release and due dates. The goal is to obtain feasible schedules by minimizing the makespan Cmax if the problem is feasible, or to obtain a ‘best compromise’ schedule if a full solution is not possible. The TS algorithm developed here is distinguished mainly by two aspects. Firstly, the core of the procedure is a tabu thresholding algorithm which uses a sophisticated set of moves aimed at resolving violated constraints. Secondly, the TS algorithm supplements the central tabu thresholding algorithm with two diversification strategies which are dependent on the state of the search. These strategies involve fairly major disruption of the schedules, and force significant diversification of the search. Computational experiments show that our algorithm can find high quality schedules in short running times.