×

A VNS algorithm for noisy problems and its application to project portfolio analysis. (English) Zbl 1175.90330

Hromkovič, Juraj (ed.) et al., Stochastic algorithms: Foundations and applications. 4th international symposium, SAGA 2007, Zurich, Switzerland, September 13–14, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74870-0/pbk). Lecture Notes in Computer Science 4665, 93-104 (2007).
Summary: Motivated by an application in project portfolio analysis under uncertainty, we develop an algorithm S-VNS for solving stochastic combinatorial optimization (SCO) problems based on the Variable Neighborhood Search (VNS) metaheuristic, and show its theoretical soundness by a mathematical convergence result. S-VNS is the first general-purpose algorithm for SCO problems using VNS. It combines a classical VNS search strategy with a sampling approach with suitably increasing sample size. After the presentation of the algorithm, the considered application problem in project management, which combines a project portfolio decision on an upper level and project scheduling as well as staff assignment decisions on a lower level, is described. Uncertain work times require a treatment as an SCO problem. First experimental results on the application of S-VNS to this problem are outlined.
For the entire collection see [Zbl 1129.68004].

MSC:

90C27 Combinatorial optimization
90B36 Stochastic scheduling theory in operations research
90C15 Stochastic programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI