Review of optimization methods for combinatorial job-shop scheduling problem
This article describes the importance of scheduling, provides a formal statement of the combinatorial job-shop scheduling problem, and shows the complexity of the problem. A review of the most common methods of exact and approximate methods was given. For each method examples was listed and the methods was analysis applied to the job-shop scheduling problems, strengths and weaknesses of the methods were identified. Brute force method theoretically allows to find the exact solution, but is not used, as it is time-consuming. Direct enumeration methods such as brand and bound, are applicable only for some particular cases. Are more efficient algorithms that, firstly, the problem is solved repeatedly and gradually formed the final decision based on the experience of previous decisions, and secondly, using randomization and approaches based on the mechanisms used by nature. These algorithms include Simulated Annealing, Tabu Search, Evolutionary algorithms and Swarm Intelligence algorithms. These algorithms require the parameters settings, so for the best performance the algorithms should be tuned to adapt to the conditions of the problem, in other words, to apply mechanisms meta-optimization and machine learning.