Solving the Dynamic Job Shop Scheduling Problem using Bottleneck and Intelligent Agents based on Genetic Algorithm

Abstract

The problem of Dynamic Job Shop (DJS) scheduling is one of the most complex problems of machine scheduling. This problem is one of NP-Hard problems for solving which numerous heuristic and metaheuristic methods have so far been presented. Genetic Algorithms (GA) are one of these methods which are successfully applied to these problems. In these approaches, of course, better quality of solutions, avoiding premature convergence, and robustness of solutions is still among the challenging arguments and in the researchers’ center of attention. The investigations in real manufacturing environments indicate that many of these systems have Bottleneck Recourses (BR). According to the concepts of the Theory of Constraint (TOC), the output of manufacturing systems is limited based on BR capacity. Hence, for improving system performance, one must find and investigate the improvement of BR effects in different levels of decision-making. Moreover, the capacity of these resources should be improved to the maximum possible limit. In this study, for detecting and using BR in shop floor decisions (e.g. scheduling), a new detection method of bottleneck for DJS problems known as bottleneck detection method based on Taguchi Approach (TA-DJS) has been developed. On the other hand, the adapting of GA operators in amount and range of coverage can operate as an efficient approach in improving its operation and effectiveness. In this way, the adapting for operators prevents its premature convergence and the adapting in the range of coverage causes maximum use of the problem’s important resources and better performance of the algorithm in each step of its run. In the proposed GA (GAIA), initially the adapting in the amount of algorithm’s operators based on the solutions’ tangent rate for premature convergence is done, then the adapting in the range of coverage of operators’ algorithm, in first step, happens by operators convergence on BR (which was detected initially) and, in the next step, occurs by operators convergence on the elite solutions so that the search process focuses on more probable ranges than the whole range of solution. Comparing the problem results in the static state with the results of other available methods in the literature indicated high efficiency of the proposed method.