The paper is dealing with parallelized versions of simulated annealing-based heuristics for the classical job shop scheduling problem. The scheduling problem is represented by the disjunctive graph model and the objective is to minimize the length of longest paths. The problem is formulated for l jobs where each job has to process exactly one task on each of the m machines. The calculation of longest paths is the critical computation step of our heuristics and we utilize a parallel algorithm for this particular problem where we take into account the specific properties of job shop scheduling. In our heuristics, we employ a neighborhood relation which was introduced by Van Laarhoven et al. To obtain a neighbor, a single arc from a longest path is reversed and these transition steps always guarantee the feasibility of schedules. We designed two cooling schedules for homogeneous Markov chains and additionally we investigated a logarithmic cooling schedule for inhomogeneous Markov chains. Given O(n3) processors and a known upper bound Λ = Λ(l,m) for the length of longest paths, the expected run-times of parallelized versions are O(n log n log Λ) for the first cooling schedule and O(n2(log3/2n)m1/2 log Λ)for the second cooling schedule, where n = lm is the number of tasks. For the logarithmic cooling schedule, a speed-up of O(n/(log n log Λ)) can be achieved. When Markov chains of constant length are assumed, we obtain a polylogarithmic run-time of O(log n log Λ) for the first cooling schedule. The analysis of famous benchmark problems led us to the conjecture that Λ ⩽ O(l + m) could be a uniform upper bound for the completion time of job shop scheduling problems with l jobs on m machines. Although the number of processors is very large, the particular processors are extremely simple and the parallel processing system is suitable for hardware implementations.
