[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

A preemptive bound for the Resource Constrained Project Scheduling Problem

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

The Resource Constrained Project Scheduling Problem is one of the most intensively investigated scheduling problems. It requires scheduling a set of interrelated activities, while considering precedence relationships, and limited renewable resources allocation. The objective is to minimize the project duration. We propose a new destructive lower bound for this challenging \({\mathcal {NP}}\)-hard problem. Starting from a previously suggested LP model, we propose several original valid inequalities that aim at tightening the model representation. These new inequalities are based on precedence constraints, incompatible activity subsets, and nonpreemption constraints. We present the results of an extensive computational study that was carried out on 2,040 benchmark instances of PSPLIB, with up to 120 activities, and that provide strong evidence that the new proposed lower bound exhibits an excellent performance. In particular, we report the improvement of the best known lower bounds of 5 instances.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Alvarez-Valdés, R., & Tamarit, M. (1993). The project scheduling polyhedron: Dimension, facets and lifting theorems. European Journal of Operational Research, 67, 204–220.

    Article  Google Scholar 

  • Artigues, C., Demassey, S., & Néron, E. (2008). Resource-constrained project scheduling : Models, algorithms, extensions and applications. New York: Wiley.

    Book  Google Scholar 

  • Baptiste, P., & Demassey, S. (2004). Tight LP bounds for resource constrained project scheduling. OR Spectrum, 26, 251–262.

    Article  Google Scholar 

  • Baptiste, P., Le Pape, C., & Nuijten, W. (1999). Satisfiability tests and time-bound adjustments for cumulative scheduling problems. Annals of Operations Research, 92, 305–333.

    Article  Google Scholar 

  • Brucker, P., & Knust, S. (2000). A linear programming and constraint propagation-based lower bound for the RCPSP. European Journal of Operational Research, 127, 355–362.

    Article  Google Scholar 

  • Carlier, J., Clautiaux, F., & Moukrim, A. (2007). New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation. Computers & Operations Research, 34, 2223–2250.

    Google Scholar 

  • Carlier, J., & Latapie, B. (1991). Une méthode arborescente pour résoudre les problèmes cumulatifs. RAIRO-RO, 25, 311–340.

    Google Scholar 

  • Carlier, J., & Néron, E. (2000). A new LP-based lower bound for the cumulative scheduling problem. European Journal of Operational Research, 127, 363–382.

    Article  Google Scholar 

  • Carlier, J., & Néron, E. (2003). On linear lower bounds for the resource constrained project scheduling problem. European Journal of Operational Research, 149, 314–324.

    Article  Google Scholar 

  • Christofides, N., Alvarez-Valdes, R., & Tamarit, J. (1987). Project scheduling with resource constraints: A branch and bound approach. European Journal of Operational Research, 29, 262–273.

    Article  Google Scholar 

  • Demeulemeester, E., & Herroelen, W. (2002). Project scheduling: a research handbook (Vol. 49). Boston: Kluwer Academic Publishers.

    Google Scholar 

  • Erschler, J., Lopez, P., & Thuriot, C. (1991). Raisonnement temporel sous contraintes de ressources et problèmes d’ordonnancement. Revue d’Intelligence Artificielle, 5, 7–32.

    Google Scholar 

  • Fekete, S., & Schepers, J. (1998). New classes of lower bounds for bin-packing problems. Lecture Notes in Computer Science, 1412, 257–270.

    Article  Google Scholar 

  • Haouari, M., Kooli, A., & Néron, E. (2012). Enhanced energetic reasoning-based lower bounds for the resource constrained project scheduling problem. Computers & Operations Research, 39, 1187–1194.

    Article  Google Scholar 

  • Klein, R., & Scholl, A. (1999). Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling. European Journal of Operational Research, 112, 322–346.

    Article  Google Scholar 

  • Kolisch, R., Sprecher, A., & Drexl, A. (1997). PSPLIB—a project scheduling library. European Journal of Operational Research, 96, 205–216.

    Article  Google Scholar 

  • Koné, O., Artigues, C., Lopez, P., & Mongeau, M. (2011). Event-based milp models for resource-constrained project scheduling problems. Computers & Operations Research, 38, 3–13.

    Article  Google Scholar 

  • Lahrichi, A. (1982). Ordonnancements: La notion de parties obligatoires et son application aux problèmes cumulatifs. RAIRO-RO, 16, 241–262.

    Google Scholar 

  • Mingozzi, A., Maniezzo, V., Ricciardelli, S., & Bianco, L. (1998). An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Management Science, 44, 714–729.

    Article  Google Scholar 

  • Möhring, R., Schulz, A., Stork, F., & Uetz, M. (2003). Solving project scheduling problems by minimum cut computations. Management Science, 49, 330–350.

    Article  Google Scholar 

  • Nabeshima, I. (1973). Algorithms and reliable heuristics programs for multiproject scheduling with resource constraints and related parallel scheduling. Tokyo: University of Electro-Communications.

    Google Scholar 

  • Östergård, P. (2001). A new algorithm for the maximum-weight clique problem. Nordic Journal of Computing, 8, 424–436.

    Google Scholar 

  • Östergård, P. (2002). A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120, 197–207.

    Article  Google Scholar 

  • Pritsker, A., Watters, L., & Wolfe, P. (1969). Multi-project scheduling with limited resources: A zero-one programming approach. Management Science, 16, 93–108.

    Article  Google Scholar 

  • Schutt, A., Feydy, T., Stuckey, P., & Wallace, M. (2011). Explaining the cumulative propagator. Constraints, 16, 250–282.

    Article  Google Scholar 

  • van den Akker, J., Diepen, G., Hoogeveen, J. (2007). A column generation based destructive lower bound for resource constrained project scheduling problems. In Proceedings of CPAIOR (pp. 376–390).

  • Vilim, P. (2011). Timetable edge finding filtering algorithm for discrete cumulative resources. Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. Lecture Notes in Computer Science, 6697, 230–245.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mechanical and Industrial Engineering, College of Engineering, Qatar University, Doha, Qatar

    Mohamed Haouari

  2. Ecole Supérieure des Sciences Economiques et Commerciales de Tunis, Université de Tunis, 4 Rue Abou Zakaria El Hafsi, 1089 , Montfleury, Tunisia

    Anis Kooli

  3. Laboratoire d’Informatique (EA 2101), Equipe Ordonnancement et Conduite (ERL CNRS 6305), Université François Rabelais de Tours, 64 avenue Jean Portalis, 37200 , Tours, France

    Anis Kooli & Emmanuel Néron

  4. Laboratoire HeuDiaSyC, CNRS UMR 7253, Université de Technologie de Compiègne, BP 20529, 60205 , Compiègne, France

    Jacques Carlier

Authors
  1. Mohamed Haouari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anis Kooli
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Emmanuel Néron
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jacques Carlier
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anis Kooli.

Appendix: New lower bounds

Appendix: New lower bounds

Table 9 lists all the improved lower bounds for the KSD instances of the PSPLIB benchmark.

Table 9 New lower bounds for KSD instances
Full size table

Rights and permissions

Reprints and permissions

About this article

Cite this article

Haouari, M., Kooli, A., Néron, E. et al. A preemptive bound for the Resource Constrained Project Scheduling Problem. J Sched 17, 237–248 (2014). https://doi.org/10.1007/s10951-013-0354-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-013-0354-9

Keywords

Search

Navigation