Gutjahr, Walter J.; Katzensteiner, Stefan; Reiter, Peter 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]. Cited in 12 Documents MSC: 90C27 Combinatorial optimization 90B36 Stochastic scheduling theory in operations research 90C15 Stochastic programming 90C59 Approximation methods and heuristics in mathematical programming Keywords:variable neighborhood search; stochastic combinatorial optimization; project portfolio selection; staff assignment; project scheduling PDFBibTeX XMLCite \textit{W. J. Gutjahr} et al., Lect. Notes Comput. Sci. 4665, 93--104 (2007; Zbl 1175.90330) Full Text: DOI