The convergence of stochastic algorithms solving flow shop scheduling

In the paper, we apply logarithmic cooling schedules of simulated annealing-based algorithms to flow shop scheduling. In our problem setting, the objective to minimize the overall completion time which is called the makespan. We prove a lower bound for the number of steps that are sufficient to approach an optimum solution with a certain probability. The result is related to the maximum escape depth Γ from local minima of the underlying energy landscape. In our approach, we need View the MathML source steps to be in an optimum solution with probability 1−δ, where n denotes the total number of tasks. The auxiliary computations are of polynomial complexity. Since the model cannot be approximated arbitrarily closely in the general case (unless View the MathML source), the approach can be used to obtain approximation algorithms that work well in the average case.