A tabu search-based approach for scheduling job-shop type flexible manufacturing systems

The problem of scheduling parts in a job-shop type flexible manufacturing system (FMS) is investigated when each part can have alternative process plans and each operation required of a part can be performed on alternative machines. The mixed-(binary) integer programming model developed for the problem is proven strongly NP-hard. A higher-level heuristic solution algorithm based on a concept known as ‘tabu search’ is developed to determine the best (near-optimal) solution for problems of industrial merit. A comparison of six different versions of tabu search-based heuristics (TSH 1–TSH 6) is performed to investigate the impact of using long-term memory and the use of fixed versus variable tabu-list sizes. A carefully constructed statistical experiment, based on randomized complete-block design, is used to test the performance on four problem structures ranging from 4 to 14 parts. The results show that, as the problem size increases, TSH 3 with fixed tabu-list size and long-term memory is preferred over the other heuristics. Further, the branch-and-bound technique, by failing to identify as good a solution as that determined by the heuristics (TSH 1–TSH 6), let alone an optimal solution, for a small problem reinforces the need for developing efficient heuristics for solving real problems encountered in industry practice.