This paper presents an approximation algorithm for the job shop scheduling problem, which aims to find the minimum makespan. The algorithm is based on simulated annealing, a method that allows the acceptance of cost-increasing transitions with a non-zero probability, thus avoiding local minima. The algorithm asymptotically converges in probability to a globally minimal solution, even though the Markov chains generated by the algorithm are not irreducible. Computational experiments show that the algorithm can find shorter make-spans than tailored heuristics, although at the expense of larger computation times. The job shop scheduling problem involves scheduling a set of jobs on a set of machines, where each job consists of a sequence of operations that must be processed on specific machines. The goal is to find a schedule that minimizes the makespan, which is the total time required to complete all operations. The problem is known to be NP-hard and is among the hardest combinatorial optimization problems. The algorithm uses a disjunctive graph model to represent the problem, where operations are nodes and edges represent constraints between operations. The algorithm generates a sequence of configurations, where each configuration represents a possible schedule. The algorithm uses a Markov chain to explore the configuration space, with transitions between configurations determined by the simulated annealing process. The algorithm is designed to find a globally minimal solution by allowing the acceptance of cost-increasing transitions with a certain probability, which decreases as the algorithm progresses. The algorithm is tested on various instances of the job shop scheduling problem, including those due to Fisher and Thompson and Lawrence. The results show that the algorithm performs slightly better than the shifting bottleneck procedure in terms of the length of the schedules returned, although the computation times can be very long. The algorithm is also compared with other heuristic methods, and it is found to be a promising and robust approach for job shop scheduling, as well as superior to traditional approaches based on priority dispatching rules. The algorithm's performance is influenced by the cooling schedule, which determines the rate at which the control parameter is decreased. The results indicate that the algorithm is effective in finding high-quality solutions, even for large problem instances.This paper presents an approximation algorithm for the job shop scheduling problem, which aims to find the minimum makespan. The algorithm is based on simulated annealing, a method that allows the acceptance of cost-increasing transitions with a non-zero probability, thus avoiding local minima. The algorithm asymptotically converges in probability to a globally minimal solution, even though the Markov chains generated by the algorithm are not irreducible. Computational experiments show that the algorithm can find shorter make-spans than tailored heuristics, although at the expense of larger computation times. The job shop scheduling problem involves scheduling a set of jobs on a set of machines, where each job consists of a sequence of operations that must be processed on specific machines. The goal is to find a schedule that minimizes the makespan, which is the total time required to complete all operations. The problem is known to be NP-hard and is among the hardest combinatorial optimization problems. The algorithm uses a disjunctive graph model to represent the problem, where operations are nodes and edges represent constraints between operations. The algorithm generates a sequence of configurations, where each configuration represents a possible schedule. The algorithm uses a Markov chain to explore the configuration space, with transitions between configurations determined by the simulated annealing process. The algorithm is designed to find a globally minimal solution by allowing the acceptance of cost-increasing transitions with a certain probability, which decreases as the algorithm progresses. The algorithm is tested on various instances of the job shop scheduling problem, including those due to Fisher and Thompson and Lawrence. The results show that the algorithm performs slightly better than the shifting bottleneck procedure in terms of the length of the schedules returned, although the computation times can be very long. The algorithm is also compared with other heuristic methods, and it is found to be a promising and robust approach for job shop scheduling, as well as superior to traditional approaches based on priority dispatching rules. The algorithm's performance is influenced by the cooling schedule, which determines the rate at which the control parameter is decreased. The results indicate that the algorithm is effective in finding high-quality solutions, even for large problem instances.