Combining hash-based Tabu search and frequent pattern mining for job-shop scheduling
提出一种混合算法，将哈希禁忌搜索与频繁模式挖掘结合，用于求解作业车间调度问题，在标准算例上改进了13个已知最优解。
The Job Shop Scheduling Problem (JSP) is a classical combinatorial optimization problem that involves scheduling a set of jobs on a set of machines to minimize the makespan. Because of its importance, the JSP has been extensively studied in the fields of operations research and manufacturing. This study presents a highly effective hybrid approach that integrates tabu search with frequent pattern mining within a population-based search framework for addressing the JSP. Of particular interest of the tabu search is its novel tabu strategy, which employs hash techniques to accurately mark visited solutions and rapidly determine the tabu status of neighboring solutions in the local search. Such a tabu strategy enables a more efficient exploration of the solution space. Furthermore, the hybrid approach fully embraces the potential of frequent pattern mining by incorporating a frequent job order recognition method to identify promising solution structures. These structures are not only used to generate new promising solutions but also to guide the local search process. Extensive experiments on the benchmark instances widely used in the literature show that the hybrid algorithm performs remarkably well, by improving 13 best-known results (new upper bounds). Additional experiments are presented to gain insight into the role of the key elements of the algorithm.