SOLVING THE JOB-SHOP SCHEDULING PROBLEM WITH TABU SEARCH

In the job shop scheduling problem we desire to minimize the makespan where a set of machines perform technologically ordered operations uni que to each member of a set of jobs. Each operation has a fixed time d uration, no machine can perform more than one operation at a time, and preemption is not allowed. In this paper, an effective tabu search ap proach to the job shop scheduling problem is presented. The procedure starts from the best solution rendered by a set of 14 heuristic dispat ching solutions. It then makes use of the classical disjunctive networ k representation of the problem and iteratively moves to another feasi ble solution by reversing the order of two adjacent critical path oper ations performed by the same machine. The concepts of historical gener ators and search restart are used in conjunction with a contiguous spe ctrum of short term memory values to enhance the overall exploration s trategy. Computational results are presented and areas for future inve stigation are suggested.