Finding Robust Solutions for the Stochastic Job Shop Scheduling Problem by Including Simulation in Local Search

摘要

Although combinatorial algorithms have been designed for problems with given, deterministic data, they are often used to find good, approximate solutions for practical problems in which the input data are stochastic variables. To compensate for the stochasticity, in many cases the stochastic data are replaced, either by some percentile of the distribution, or by the expected value multiplied by a 'robustness' factor; the resulting, deterministic instance is then solved, and this solution is run in practice. We apply a different approach based on a combination of local search and simulation. In the local search, the comparison between the current solution and a neighbor is based on simulating both solutions a number of times. Because of the flexibility of simulation, each stochastic variable can have its own probability distribution, and the variables do not have to be independent. We have applied this method to the job shop scheduling problem, where we used simulated annealing as our local search method. It turned out that this method clearly outperformed the traditional rule-of-thumb methods.