The paper "Job Shop Scheduling by Simulated Annealing" by P.J.M. van Laarhoven, E.H.L. Aarts, and J.K. Lenstra discusses an approximation algorithm for finding the minimum makespan in a job shop scheduling problem. The algorithm is based on simulated annealing, a generalization of iterative improvement, which allows for the acceptance of cost-increasing transitions with a non-zero probability to avoid getting stuck in local minima. The authors prove that the algorithm asymptotically converges to a globally minimal solution, despite the Markov chains generated by the algorithm not being irreducible. Computational experiments show that the algorithm can find shorter makespans than tailored heuristics, though at the cost of longer computation times. The paper also includes a detailed description of the problem formulation, the application of simulated annealing to job shop scheduling, and empirical results comparing the algorithm's performance with other methods.The paper "Job Shop Scheduling by Simulated Annealing" by P.J.M. van Laarhoven, E.H.L. Aarts, and J.K. Lenstra discusses an approximation algorithm for finding the minimum makespan in a job shop scheduling problem. The algorithm is based on simulated annealing, a generalization of iterative improvement, which allows for the acceptance of cost-increasing transitions with a non-zero probability to avoid getting stuck in local minima. The authors prove that the algorithm asymptotically converges to a globally minimal solution, despite the Markov chains generated by the algorithm not being irreducible. Computational experiments show that the algorithm can find shorter makespans than tailored heuristics, though at the cost of longer computation times. The paper also includes a detailed description of the problem formulation, the application of simulated annealing to job shop scheduling, and empirical results comparing the algorithm's performance with other methods.