Solving a job shop scheduling problem optimally is difficult, but when the data are uncertain, the problem is much more complicated
because of the inaccurate objective estimation, large search space, and multiple local minima. In this paper, simulated annealing incorporated with Monte-Carlo
simulation is applied to
stochastic job shop scheduling problem when the processing times are random variables with known means and variances, to minimize the expected make-span. To fine a lower bound on the performance measure, a surrogate simulated annealing is proposed, in which an extra penalty term is added to each of the expected value of the random processing times to approximately account to some variations in the problem data. The effects of some parameters on both algorithms are also discussed.