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

Guido Passage (), Marjan van den Akker () and Han Hoogeveen ()
Additional contact information
Guido Passage: ORTEC
Marjan van den Akker: Utrecht University
Han Hoogeveen: Utrecht University

Journal of Heuristics, 2025, vol. 31, issue 3, No 1, 31 pages

Abstract: Abstract 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.

Keywords: Metaheuristics; Stochastic scheduling; Simulation; Approximation of probability distribution; Normal Distribution (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09562-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:3:d:10.1007_s10732-025-09562-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09562-5

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().