IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v43y1996i1p23-40.html
   My bibliography  Save this article

Adaptive search for solving hard project scheduling problems

Author

Listed:
  • Rainer Kolisch
  • Andreas Drexl

Abstract

In this article we propose a new heuristic solution technique for resource‐constrained project scheduling problems. Basically, it is a hybrid of priority rule and random search techniques which employs two types of adaptations in order to determine the solution space. We enhance this general scheme by the use of a new priority rule and by lower bounding techniques. The method is evaluated by comparing it with other recently proposed heuristics on a widely used set of benchmark‐instances. Furthermore, we show that the procedure can be usefully applied to solve different hard problems within the field of project scheduling. © 1996 John Wiley & Sons, Inc.

Suggested Citation

  • Rainer Kolisch & Andreas Drexl, 1996. "Adaptive search for solving hard project scheduling problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(1), pages 23-40, February.
    • Handle: RePEc:wly:navres:v:43:y:1996:i:1:p:23-40
    DOI: 10.1002/(SICI)1520-6750(199602)43:13.0.CO;2-P
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/(SICI)1520-6750(199602)43:13.0.CO;2-P
    Download Restriction: no
    File URL: https://libkey.io/10.1002/(SICI)1520-6750(199602)43:13.0.CO;2-P?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Oguz, Osman & Bala, Hasan, 1994. "A comparative study of computational procedures for the resource constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 72(2), pages 406-416, January.
    2. Deckro, RF & Hebert, JE, 1989. "Resource constrained project crashing," Omega, Elsevier, vol. 17(1), pages 69-79.
    3. Edward W. Davis & James H. Patterson, 1975. "A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling," Management Science, INFORMS, vol. 21(8), pages 944-955, April.
    4. Erik Demeulemeester & Willy Herroelen, 1992. "A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 38(12), pages 1803-1818, December.
    5. Colin E. Bell & Jaemin Han, 1991. "A new heuristic solution method in resource‐constrained project scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(3), pages 315-331, June.
    6. Dale F. Cooper, 1976. "Heuristics for Scheduling Resource-Constrained Projects: An Experimental Investigation," Management Science, INFORMS, vol. 22(11), pages 1186-1194, July.
    7. Jerome D. Wiest, 1967. "A Heuristic Model for Scheduling Large Projects with Limited Resources," Management Science, INFORMS, vol. 13(6), pages 359-377, February.
    8. Rainer Kolisch & Arno Sprecher & Andreas Drexl, 1995. "Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems," Management Science, INFORMS, vol. 41(10), pages 1693-1703, October.
    9. Scott E. Sampson & Elliott N. Weiss, 1993. "Local search techniques for the generalized resource constrained project scheduling problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(5), pages 665-675, August.
    10. Yau, Chuk & Ritchie, Eric, 1990. "Project compression: A method for speeding up resource constrained projects which preserve the activity schedule," European Journal of Operational Research, Elsevier, vol. 49(1), pages 140-152, November.
    11. Li, K. Y. & Willis, R. J., 1992. "An iterative scheduling technique for resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 56(3), pages 370-379, February.
    12. Andreas Drexl, 1991. "Scheduling of Project Networks by Job Assignment," Management Science, INFORMS, vol. 37(12), pages 1590-1602, December.
    13. James H. Patterson, 1984. "A Comparison of Exact Approaches for Solving the Multiple Constrained Resource, Project Scheduling Problem," Management Science, INFORMS, vol. 30(7), pages 854-867, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. André Schnabel & Carolin Kellenbrink & Stefan Helber, 2018. "Profit-oriented scheduling of resource-constrained projects with flexible capacity constraints," Business Research, Springer;German Academic Association for Business Research, vol. 11(2), pages 329-356, September.
    2. Sepehr Proon & Mingzhou Jin, 2011. "A genetic algorithm with neighborhood search for the resource‐constrained project scheduling problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(2), pages 73-82, March.
    3. Osman Hürol Türkakın & David Arditi & Ekrem Manisalı, 2021. "Comparison of Heuristic Priority Rules in the Solution of the Resource-Constrained Project Scheduling Problem," Sustainability, MDPI, vol. 13(17), pages 1-17, September.
    4. Andreas Schirmer, 2000. "Case‐based reasoning and improved adaptive search for project scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(3), pages 201-222, April.
    5. Sönke Hartmann, 2002. "A self‐adapting genetic algorithm for project scheduling under resource constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(5), pages 433-448, August.
    6. Dieter Debels & Mario Vanhoucke, 2007. "A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem," Operations Research, INFORMS, vol. 55(3), pages 457-469, June.
    7. Sönke Hartmann, 1998. "A competitive genetic algorithm for resource‐constrained project scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(7), pages 733-750, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    2. Kolisch, Rainer, 1996. "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation," European Journal of Operational Research, Elsevier, vol. 90(2), pages 320-333, April.
    3. Kolisch, Rainer & Drexl, Andreas, 1994. "Hybrid biased random sampling for multiple resourse-constrained project scheduling problems," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 354, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    4. Kolisch, Rainer, 1994. "Serial and parallel resource-constrained projekt scheduling methodes revisited: Theory and computation," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 344, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    5. Jan Böttcher & Andreas Drexl & Rainer Kolisch & Frank Salewski, 1999. "Project Scheduling Under Partially Renewable Resource Constraints," Management Science, INFORMS, vol. 45(4), pages 543-559, April.
    6. Schirmer, Andreas & Riesenberg, Sven, 1997. "Parameterized heuristics for project scheduling: Biased random sampling methods," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 456, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    7. Aristide Mingozzi & Vittorio Maniezzo & Salvatore Ricciardelli & Lucio Bianco, 1998. "An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation," Management Science, INFORMS, vol. 44(5), pages 714-729, May.
    8. Böttcher, Jan & Drexl, Andreas & Kolisch, Rainer & Salewski, Frank, 1996. "Project scheduling under partially renewable resource constraints," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 398, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    9. Kolisch, Rainer, 1994. "Efficient priority rules for the resource-constrained project scheduling problem," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 350, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    10. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    11. Salewski, Frank & Schirmer, Andreas & Drexl, Andreas, 1997. "Project scheduling under resource and mode identity constraints: Model, complexity, methods, and application," European Journal of Operational Research, Elsevier, vol. 102(1), pages 88-110, October.
    12. Schirmer, Andreas & Riesenberg, Sven, 1998. "Class-based control schemes for parameterized project scheduling heuristics," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 471, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    13. Rainer Kolisch, 1999. "Resource Allocation Capabilities of Commercial Project Management Software Packages," Interfaces, INFORMS, vol. 29(4), pages 19-31, August.
    14. Drexl, Andreas & Kolisch, Rainer & Sprecher, Arno, 1995. "Neuere Entwicklungen in der computergestützten Projektplanung," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 379, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    15. Kolisch, Rainer & Hartmann, Sonke, 2006. "Experimental investigation of heuristics for resource-constrained project scheduling: An update," European Journal of Operational Research, Elsevier, vol. 174(1), pages 23-37, October.
    16. Kolisch, Rainer & Hempel, Kai, 1996. "Finite scheduling capabilities of commercial project management systems," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 397, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    17. Kolisch, Rainer & Sprecher, Arno & Drexl, Andreas, 1992. "Characterization and generation of a general class of resource-constrained project scheduling problems: Easy and hard instances," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 301, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    18. Yang, Kum-Khiong, 1998. "A comparison of dispatching rules for executing a resource-constrained project with estimated activity durations," Omega, Elsevier, vol. 26(6), pages 729-738, December.
    19. Sönke Hartmann, 1998. "A competitive genetic algorithm for resource‐constrained project scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(7), pages 733-750, October.
    20. Sprecher, Arno, 1996. "Solving the RCPSP efficiently at modest memory requirements," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 425, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:43:y:1996:i:1:p:23-40. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.