Job-shop scheduling is one of the core research aspects of Manufacturing Execution System (MES). It is significant for improving the utilization of enterprise resources, enhancing product quality, shortening delivery periods, reducing product cost, and raising enterprise competitive power in market economy. In order to solve this problem, Simulated Annealing (SA) algorithm is improved to solve large-scale combinatorial problem of job-shop scheduling. To make the SA algorithm more effective to solve job-shop scheduling problems, a solution encoding mode, scheduling scheme generation, initial temperature selection, temperature updating function, Markov chain length, end rule, and so on of the improved SA algorithm are discussed that affect the computation speed and convergence of the SA algorithm. Finally, the improved SA algorithm is validated by a job–shop scheduling problem of 10 workpieces and 10 machines.