Distributed Simulated Annealing for Job Shop Scheduling.

In the paper, we investigate theoretical and practical aspects of distributed computing for simulated annealing algorithms applied to the problem of scheduling l jobs on m machines. Given n = l · m, the total number of tasks, O(n3) processors and an upper bound Λ = Λ(l, m) of the objective function, the expected run-times of parallelized versions of our heuristics [14] are O(n · log n · log Λ) for the exponential cooling schedule and O(n2 · log3/2n · m1/2 · log Λ) for the hyperbolic one. For Markov chains of constant length, the results imply a polylogarithmic run-time O(log n · log(l + m)) for the exponential schedule, where we employ Λ ≤ O(l + m), see Leighton et al. [10]. We implemented a distributed version of our sequential heuristics and first computational experiments on benchmark instances are presented. [ABSTRACT FROM AUTHOR]