Hybrid Tabu search & Beam Search algorithm for Job Shop scheduling

A scheduling algorithm using search tree creation and a search policy based on the problem structure information is proposed for solving larger scale Job Shop problems by minimizing the makespan using a tabu search and a beam search. The beam search mechanism for the algorithm iteration selectively divaricates the solution space and selectively evaluaties the corresponding divisions. The tabu search with a strong local search is used to evaluate each division to determine the ideal divisions suitable for the Beam Search iteration to reduce the possibility of the Beam Search cutting off good solutions. Numerical results with 40 benchmark examples of Job Shop problems minimizing the makespan show that the algorithm is efficient and that the solution quality is satisfactory so the algorithm is suitable for large scale scheduling problems.