A new, efficient approach to speed up local search by estimating the solution quality: an application to stochastic, parallel machine scheduling

Local search has become a very powerful tool to solve hard optimization problems. One of the key parts here is that you must decide to accept or reject a new solution, for which we compare the objective values of the incumbent and the new solution. Since in general very many iterations are involved, it is important that this comparison can be done efficiently. In case of a stochastic problem, where we want to optimize the expected value, it is often impossible to do the comparison analytically. We can resolve this by simulating a solution, but to find an accurate estimate we need many simulations, which may take a lot of time. In this paper we present an alternative method to estimate the expected value for problems involving waiting relations. To apply this method we must iteratively compute the maximum of several stochastic variables. Thereto, we pretend that all stochastic variables are normally distributed, after which we iteratively estimate the expected value and standard deviation of the maximum of two variables; in the further analysis we pretend this maximum to be normally distributed again. We test the efficiency of this method on a specific scheduling problem with precedence relations. In our experiments we find that this approximation method in many cases produces better solutions than estimating the expected makespan using 1000 independent simulations per iteration, and it always dominates using 300 simulations per iteration, while using only a fraction of the time. Moreover, this method of estimating the distribution of the maximum seems to be widely applicable. For example, we can use it for all kinds of planning problems in which a person/task must wait until at least two other events have been completed, which is a typical situation in which a direct computation of the expected value is intractable.