An interactive high speed scheduling method by tabu search for a large-scale job shop problem with group constraints

The target of this research is a job shop problem with group constraints consisting of about 2000 jobs. It focuses on how jobs are grouped and processed. In this problem, evaluation factors are different according to the characteristics of each problem, and some evaluation factors are difficult to formulate. Therefore, it is difficult for a computer to strictly evaluate the schedule. In this research, the interactive system that can adapt to an expert´s demands is realized. However, it is difficult to remake solutions using the existing scheduling method under the time constraints that require three or four interactive inputs in one hour. This system improves the current solutions created using tabu search to achieve high-speed interaction. A solution that satisfies experts is created by repeating this method. Demands and dispatching rules are prepared in order to satisfy the demands. The solution is improved using a tabu search that can apply some of these rules. For effective improvement, an efficient application method of these rules is proposed. In the proposed method, rules are classified by their features into three categories and the application rate of each category is dynamically changed. The proposed method is applied to some real problems. The solutions are improved within 20 minutes against a set of input demands. The method can be said to be effective because a good schedule can be made in three or four interactions within one hour