An Efficient Hybrid Search Algorithm for Various Optimization Problems | SpringerLink
Skip to main content
Springer Nature Link
Log in

An Efficient Hybrid Search Algorithm for Various Optimization Problems

  • Conference paper
Evolutionary Computation in Combinatorial Optimization (EvoCOP 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3906))

Abstract

This paper describes a detailed study of a recursive search algorithm for different optimization problems. Although the algorithm has been originally developed for a project scheduling problem with financial objectives, we show that it can be extended to many other application areas and therefore, can serve as a sub-procedure for various optimization problems. The contribution of the paper is threefold. First, we present a hybrid recursive search procedure for the project scheduling problem with net present value maximization and compare it with state-of-the-art procedures by means of computational tests. Second, we show how the procedure can be adapted to two other application areas: project scheduling with work continuity minimization and the open pit mining problem. Last, we highlight some future research areas where this hybrid procedure might bring a promising contribution.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Battersby, A.: Network analysis for planning and scheduling. Macmillan, Basingstoke (1964)

    MATH  Google Scholar 

  2. Bartusch, M., Möhring, R.H., Radermacher, F.J.: Scheduling project networks with recource constraints and time windows. Annals of Operations Research 16, 201–240 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  3. Dayanand, N., Padman, R.: The payment scheduling problem in project networks. Working Paper 9331, The Heinz School, CMU, Pittsburgh, PA 15213, USA (1993)

    Google Scholar 

  4. Dayanand, N., Padman, R.: Payments in projects: a constractor’s model. Working Paper 9371, The Heinz School, CMU, Pittsburgh, PA 15213, USA (1993)

    Google Scholar 

  5. Dayanand, N., Padman, R.: On modeling payments in project networks. Journal of the Operational Research Society 48, 906–918 (1997)

    Article  MATH  Google Scholar 

  6. Demeulemeester, E., Herroelen, W., Van Dommelen, P.: An optimal recursive search procedure for the deterministic unconstrained max-npv project scheduling problem. Research Report 9603, Department of Applied Economics, Katholieke Universiteit Leuven, Belgium (1996)

    Google Scholar 

  7. De Reyck, B.: Scheduling Projects with Generalized Precedence Relations - Exact and Heuristic Procedures. Ph.D. Dissertation, Department of Applied Economics, Katholieke Universiteit Leuven, Belgium (1998)

    Google Scholar 

  8. De Reyck, B., Herroelen, W.: An optimal procedure for the unconstrained max-npv project scheduling problem with generalized precedence relations. Research Report 9642, Department of Applied Economics, Katholieke Universiteit Leuven, Belgium (1996)

    Google Scholar 

  9. De Reyck, B., Herroelen, W.: An optimal procedure for the resource-constrained project scheduling problem with discounted cash flows and generalized precedence relations. Computers and Operations Research 25, 1–17 (1998)

    Article  MATH  Google Scholar 

  10. Elmaghraby, S.E., Herroelen, W.: The scheduling of activities to maximize the net present value of projects. European Journal of Operational Research 49, 35–49 (1990)

    Article  Google Scholar 

  11. El-Rayes, K., Moselhi, O.: Resource-driven scheduling of repetitive activities. Construction Management and Economics 16, 433–446 (1998)

    Article  Google Scholar 

  12. Etgar, R., Shtub, A., LeBlanc, L.J.: Scheduling projects to maximize net present value - The case of time-dependent, contingent cash flows. European Journal of Operational Research 96, 90–96 (1996)

    Article  MATH  Google Scholar 

  13. Etgar, R., Shtub, A.: Scheduling project activities to maximize the net present value - The case of linear time dependent, contingent cash flows. International Journal of Production Research 37, 329–339 (1999)

    Article  MATH  Google Scholar 

  14. Faaland, B., Kim, K., Schmitt, T.: A new algorithm for computing the maximal closure of a graph. Management Science 36, 315–331 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  15. Grinold, R.C.: The payment scheduling problem. Naval Research Logistics Quarterly 19, 123–136 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  16. Herroelen, W., Gallens, E.: Computational experience with an optimal procedure for the scheduling of activities to maximize the net present value of projects. European Journal of Operational Research 65, 274–277 (1993)

    Article  MATH  Google Scholar 

  17. Herroelen, W., Demeulemeester, E., Van Dommelen, P.: Project network models with discounted cash flows: A guided tour through recent developments. European Journal of Operational Research 100, 97–121 (1997)

    Article  MATH  Google Scholar 

  18. Herroelen, W., Demeulemeester, E., De Reyck, B.: A classification scheme for project scheduling problems. In: Weglarz, J. (ed.) Handbook on Recent Advances in Project Scheduling, ch. 1, pp. 1–26. Kluwer Academic Publishers, Dordrecht (1999)

    Google Scholar 

  19. Hochbaum, D.S., Chen, A.: Performance analysis and best implementations of old and new algorithms for the open-pit mining problem. Operations Research 48, 894–914 (2000)

    Article  Google Scholar 

  20. Kamburowski, J.: Maximizing the project net present value in activity networks under generalized precedence relations. In: Proceeding of 21st DSI Annual meeting, San Diego, pp. 748–750 (1990)

    Google Scholar 

  21. Kazaz, B., Sepil, C.: Project scheduling with discounted cash flows and progress payments. Journal of the Operational Research Society 47, 1262–1272 (1996)

    Article  MATH  Google Scholar 

  22. Möhring, R.H., Schulz, A.S., Stork, F., Uetz, M.: On project scheduling with irregular starting time costs. Operations Research Letters 28, 149–154 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  23. Neumann, K., Zimmermann, J.: Exact and heuristic procedures for net present value and resource levelling problems in project scheduling. European Journal of Operational Research 127, 425–443 (2000)

    Article  MATH  Google Scholar 

  24. Picard, J.C.: Maximal closure of a graph and applications to combinatorial problems. Management Science 22, 1268–1272 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  25. Russell, A.H.: Cash flows in networks. Management Science 16, 357–373 (1970)

    Article  MATH  Google Scholar 

  26. Schwindt, C., Zimmermann, J.: Maximizing the net present value of projects subject to temporal constraints. WIOR-Report-536, Institut für Wirtschaftstheorie und Operations Research, University of Karlsruhe, Germany (1998)

    Google Scholar 

  27. Schwindt, C., Zimmermann, J.: A steepest ascent approach to maximizing the net present value of projects. Mathematical Methods of Operations Research 53, 435–450 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  28. Sepil, C., Ortaç, N.: Performance of the heuristic procedures for constrained projects with progress payments. Journal of the Operational Research Society 48, 1123–1130 (1997)

    Article  MATH  Google Scholar 

  29. Shtub, A., Etgar, R.: A branch-and-bound algorithm for scheduling projects to maximize net present value: the case of time dependent, contingent cash flows. International Journal of Production Research 35, 3367–3378 (1997)

    Article  MATH  Google Scholar 

  30. Vanhoucke, M.: Work continuity constraints in project scheduling. Journal of Construction Engineering and Management 132, 1–12 (2006)

    Article  Google Scholar 

  31. Vanhoucke, M., Demeulemeester, E., Herroelen, W.: An exact procedure for the resource-constrained weighted earliness-tardiness project scheduling problem. Annals of Operations Research 102, 179–196 (2000)

    Article  MATH  Google Scholar 

  32. Vanhoucke, M., Demeulemeester, E., Herroelen, W.: On maximizing the net present value of a project under renewable resource constraints. Management Science 47, 1113–1121 (2001)

    Article  MATH  Google Scholar 

  33. Vanhoucke, M., Demeulemeester, E., Herroelen, W.: Scheduling projects with linearly time-dependent cash flows to maximize the net present value. International Journal of Production Research 39, 3159–3181 (2001)

    Article  MATH  Google Scholar 

  34. Vanhoucke, M., Demeulemeester, E., Herroelen, W.: Progress payments in project scheduling problems. European Journal of Operational Research 148, 604–620 (2003)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Ghent University, Hoveniersberg 24, 9000, Ghent, Belgium

    Mario Vanhoucke

  2. Vlerick Leuven Gent Management School, Reep 1, 9000, Ghent, Belgium

    Mario Vanhoucke

Authors
  1. Mario Vanhoucke
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. SAP AG, Neurottstr. 16, 69190, Walldorf, Germany

    Jens Gottlieb

  2. Institute of Computer Graphics and Algorithms, Vienna University of Technology, Favoritenstraße 9–11/1861, 1040, Vienna, Austria

    Günther R. Raidl

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Vanhoucke, M. (2006). An Efficient Hybrid Search Algorithm for Various Optimization Problems. In: Gottlieb, J., Raidl, G.R. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2006. Lecture Notes in Computer Science, vol 3906. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11730095_23

Download citation

  • DOI: https://doi.org/10.1007/11730095_23

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-33178-0

  • Online ISBN: 978-3-540-33179-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation