Abstract
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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Alrefaei, M.H., Andradottir, S.: A Simulated Annealing algorithm with constant temperature for discrete stochastic optimization. Management Sci. 45, 748–764 (1999)
Alrefaei, M.H., Andradottir, S.: A modification of the stochastic ruler method for discrete stochastic optimization. European J. of Operational Research 133, 160–182 (2001)
Chen, A.N.K., Edgington, T.M.: Assessing value in organizational knowledge creation: considerations for knowledge workers. MIS Quaterly 29, 279–309 (2005)
Fitzpatrick, J.M., Grefenstette, J.J.: Genetic algorithms in noisy environments. Machine Learning 3, 101–120 (1988)
Fu, M.C.: Optimization for simulation: theory vs. practice. INFORMS J. on Computing 14, 192–215 (2002)
Gabriel, S.A., Kumar, S., Ordonez, J., Nasserian, A.: A multiobjective optimization model for project selection with probabilistic considerations. Socio-Economic Planning Sciences 40, 297–313 (2006)
Gelfand, S.B., Mitter, S.K.: Simulated Annealing with noisy or imprecise measurements. J. Optim. Theory Appl. 69, 49–62 (1989)
Gutjahr, W.J., Pflug, G.: Simulated annealing for noisy cost functions. J. of Global Optimization 8, 1–13 (1996)
Gutjahr, W.J.: A converging ACO algorithm for stochastic combinatorial optimization. In: Albrecht, A.A., Steinhöfel, K. (eds.) SAGA 2003. LNCS, vol. 2827, pp. 10–25. Springer, Heidelberg (2003)
Gutjahr, W.J.: S-ACO: An ant-based approach to combinatorial optimization under uncertainty. In: Dorigo, M., Birattari, M., Blum, C., Gambardella, L.M., Mondada, F., Stützle, T. (eds.) ANTS 2004. LNCS, vol. 3172, pp. 238–249. Springer, Heidelberg (2004)
Gutjahr, W.J., Katzensteiner, S., Reiter, P.: Stummer, Ch., Denk, M., Competence-driven project portfolio selection, scheduling and staff assignment, Tech. Rep. Univ. of Vienna, Dept. of Statistics and Decision Support Systems (2007)
Gutjahr, W.J., Katzensteiner, S., Reiter, P.: Variable neighborhood search for noisy problems applied to project portfolio analysis, Tech. Rep., Univ. of Vienna, Dept. of Statistics and Decision Support Systems (2007)
Hansen, P., Mladenović, N.: Variable neighborhood search: Principles and applications. European J. of Operational Research 130, 449–467 (2001)
Homem-de-Mello, T.: Variable-sample methods for stochastic optimization, ACM Trans. on Modeling and Computer Simulation 13, 108–133 (2003)
Möhring, R.H., Stork, F.: Linear preselective policies for stochastic project scheduling. Mathematical Methods of Operations Research 52, 501–515 (2000)
Nozic, L.K., Turnquist, M.A., Xu, N.: Managing portfolios of projects under uncertainty. Annals of Operations Research 132, 243–256 (2004)
Norkin, V.I., Ermoliev, Y.M., Ruszczynski, A.: On optimal allocation of indivisibles under uncertaint. Operations Research 46, 381–395 (1998)
Shi, L., Olafsson, S.: Nested partitions method for global optimization, Operations Research 48, 390–407 (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gutjahr, W.J., Katzensteiner, S., Reiter, P. (2007). A VNS Algorithm for Noisy Problems and Its Application to Project Portfolio Analysis. In: Hromkovič, J., Královič, R., Nunkesser, M., Widmayer, P. (eds) Stochastic Algorithms: Foundations and Applications. SAGA 2007. Lecture Notes in Computer Science, vol 4665. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74871-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-74871-7_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74870-0
Online ISBN: 978-3-540-74871-7
eBook Packages: Computer ScienceComputer Science (R0)