Expert-tabu search for job-shop scheduling

The aim of this thesis is to develop a scheduling model using the intelligent pronlem solving approaches for deterministic job-shop scheduling. To do this, first of all the properties of the problem were examined and the current solution approaches in literature reviewed. The literature review revealed that the scheduling model must contain the approaches using the intelligent problem solving methodology with the ability to explore the search space widely. Thus, expert systems and tabu search issues are dealt with in more detail. The target scheduling system predicts that an expert system module is will produce an initial solution which will then be improved by a tabu search module. The reason why the scheduling system contains expert systems is that they can produce solutions different from the classic methods and can manage the multi-criteria in scheduling environment. Similarly, tabu search has the ability to provide the search facilities which are more comprehensive and more effective. The scheduling system was developed step by step. In the first phase, in order to prodece an initial solution, a prototype of the expert system which has a knowledge base managing the simple priority dispatching rules was developed. In the second phase, a tabu search framework was built and some of their important parameters' values were fixed by using some benchmark problems. In the final phase, an experimental design taking in the consideration the combination of different values of shop load and job due dates yeilded nine system states. For ech system state thirty test problems were generated. The test problems produced were solved by three methods. These are several simple priority dispatching rules, the expert system prototype, and the tabu search module with initial expert system solution. Next, the results obtained from each method were statistically analised and and interpred. The experimetal results indicated that the solutions of the tabu search method numerically are 1 6.74% better than that of the simple priority dispatching rules and only approximately 5% worse than that of the optimal. This showed that the expert systems are superior to the simple priority dispatching rules and that the tabu search method with initial expert system solution produces near-optimal solutions. Consequently, the feasibility of the target scheduling system has been statistically proven.Keywords : production scheduling, expert systems, tabu search