A TABU SEARCH-BASED APPROACH FOR SCHEDULING JOB-SHOP TYPE FLEXIBLE MANUFACTURING SYSTEMS

The problem of scheduling parts in a job-shop type flexible manufactur ing system (FMS) is investigated when each part can have alternative p rocess plans and each operation required of a part can be performed on alternative machines. The mixed-(binary) integer programming model de veloped for the problem is proven strongly NP-hard. A higher-level heu ristic 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 se arch-based heuristics (TSH 1-TSH 6) is performed to investigate the im pact of using long-term memory and the use of fixed versus variable ta bu-list sizes. A carefully constructed statistical experiment, based o n randomized complete-block design, is used to test the performance on four problem structures ranging from 4-14 parts. The results show tha t, 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 goad a solution as that determined by the heuristics(TSH I-TSH 6), let alone an optima l, solution, for a small problem reinforces the need for developing ef ficient heuristics for solving real problems encountered in industry p ractice.