# Flow Polyhedra and Resource Constrained Project Scheduling Problems

Alain Quilliot; Hélène Toussaint

RAIRO - Operations Research - Recherche Opérationnelle (2012)

- Volume: 46, Issue: 4, page 373-409
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topQuilliot, Alain, and Toussaint, Hélène. "Flow Polyhedra and Resource Constrained Project Scheduling Problems." RAIRO - Operations Research - Recherche Opérationnelle 46.4 (2012): 373-409. <http://eudml.org/doc/275095>.

@article{Quilliot2012,

abstract = {This paper aims at describing the way Flow machinery may be used in order to deal with Resource Constrained Project Scheduling Problems (RCPSP). In order to do it, it first introduces the Timed Flow Polyhedron related to a RCPSP instance. Next it states several structural results related to connectivity and to cut management. It keeps on with a description of the way this framework gives rise to a generic Insertion operator, which enables programmers to design greedy and local search algorithms. It ends with numerical experiments.},

author = {Quilliot, Alain, Toussaint, Hélène},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {scheduling with resource constraints; network flow theory},

language = {eng},

number = {4},

pages = {373-409},

publisher = {EDP-Sciences},

title = {Flow Polyhedra and Resource Constrained Project Scheduling Problems},

url = {http://eudml.org/doc/275095},

volume = {46},

year = {2012},

}

TY - JOUR

AU - Quilliot, Alain

AU - Toussaint, Hélène

TI - Flow Polyhedra and Resource Constrained Project Scheduling Problems

JO - RAIRO - Operations Research - Recherche Opérationnelle

PY - 2012

PB - EDP-Sciences

VL - 46

IS - 4

SP - 373

EP - 409

AB - This paper aims at describing the way Flow machinery may be used in order to deal with Resource Constrained Project Scheduling Problems (RCPSP). In order to do it, it first introduces the Timed Flow Polyhedron related to a RCPSP instance. Next it states several structural results related to connectivity and to cut management. It keeps on with a description of the way this framework gives rise to a generic Insertion operator, which enables programmers to design greedy and local search algorithms. It ends with numerical experiments.

LA - eng

KW - scheduling with resource constraints; network flow theory

UR - http://eudml.org/doc/275095

ER -

## References

top- [1] B. Abbasi, S. Shadrokh and J. Arkat, Bi-objective resource-constrained project scheduling with robustness and makespan criteria. Appl. Math. Comput.180 (2006) 146–152. Zbl1103.90039MR2263373
- [2] R.K. Ahuja, T.L. Magnanti, J.B. Orlin and M.R. Reddy, Applications of network optimization, in Network Models (Chapter 1). Handbooks Oper. Res. Manage. Sci. 7 (1995) 1–83. Zbl0833.90116MR1420866
- [3] R.V. Ahuja, T.L. Magnanti and J.B. Orlin. Network flows : theory, algorithms and applications. Prentice hall, Englewood Cliffs, N.J (1993). Zbl1201.90001MR1205775
- [4] J. Alcaraz and C. Maroto, A robust genetic algorithm for resource allocation in project scheduling. Ann. Oper. Res.102 (2001) 83–109. Zbl1024.90036MR1854420
- [5] J. Alcaraz, C. Maroto and R. Ruiz, Improving the performance of genetic algorithms for the RCPSP problem, in Proc. 9th Int. workshop on project management and scheduling (2004) 40–43.
- [6] C. Artigues and F. Roubellat, A polynomial activity insertion algorithm in a multiresource schedule with cumulative constraints and multiple nodes. EJOR127 (2000) 297–316. Zbl0990.90034
- [7] C. Artigues, P. Michelon and S. Reusser, Insertion techniques for static and dynamic resource constrained project scheduling. EJOR149 (2003) 249–267. Zbl1040.90013MR1993131
- [8] C. Artigues and C. Briand, The resource-constrained activity insertion problem with minimum and maximum time lags. J. Schedul.12 (2009) 447–460. Zbl1176.90192MR2545563
- [9] K.R. Baker, Introduction to sequencing and scheduling. Wiley, N.Y (1974).
- [10] P. Baptiste, Resource constraints for preemptive and non preemptive scheduling, MSC Thesis, University PARIS VI (1995).
- [11] P. Baptiste and S. Demassey, Tight LP-bounds for resource constrained project scheduling. OR Spectrum26 (2004) 251–262. Zbl1072.90012
- [12] P. Baptiste, P. Laborie, C. Lepape and W. Nuijten, Constraint-based scheduling and planning, in Handbook of Constraint Programming 22, edited by F. Rossi, P. Van Beek. Elsevier (2006) 759–798. Zbl1094.90002
- [13] T. Baar, P. Brucker and S. Knust, Tabu-search algorithms and lower bounds for the resource-constrained project scheduling problem, in Meta-heuristics : Advances and trends in local search paradigms for optimization, edited by S. Voss, S. Martello, I. Osman and C. Roucairol. Kluwer Academic Publishers (1998) 1–8. Zbl1074.90563MR1788681
- [14] C. Berge, Graphes et Hypergraphes. Dunod Ed (1975). Zbl0213.25702MR357173
- [15] J. Blazewiecz, K.H. Ecker, G. Schmlidt and J. Weglarcz, Scheduling in computer and manufacturing systems. 2th edn, Springer-Verlag, Berlin (1993). Zbl0816.90068
- [16] K. Bouleimen and H. Lecocq, A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. EJOR149 (2003) 268–281. Zbl1040.90015MR1993132
- [17] C. Briand, A new any-order schedule generation scheme for resource-constrained project scheduling. RAIRO - Oper. Res. (2009) 297–308. Zbl1170.90007MR2567990
- [18] P. Brucker and S. Knust, A linear programming and constraint propagation based lower bound for the RCPSP. EJOR127 (2000) 355–362. Zbl0990.90055
- [19] P. Brucker, S. Knust, A. Schoo and O. Thiele, A branch and bound algorithm for the resource constrained project scheduling problem. EJOR107 (1998) 272–288. Zbl0970.90030
- [20] P. Brucker, A. Drexl, R. Mohring, K. Neumann and E. Pesch, Resource-constrained project scheduling : notation, classification, models and methods. EJOR112 (1999) 3–41. Zbl0937.90030
- [21] J. Carlier and P. Chrétienne. Problèmes d’ordonnancements : modélisation, complexité et algorithmes. Masson Ed, Paris (1988). Zbl0774.90043
- [22] J. Carlier and E. Neron, Computing redundant resources for the resource constrained project scheduling problem. EJOR176 (2007) 1452–1463. Zbl1104.90018MR2270857
- [23] J. Carlier and E. Neron, On linear lower bounds for the resource constrained project scheduling problem. EJOR149 (2003) 314–324. Zbl1040.90017MR1993135
- [24] H. Chtourou and M. Haouari, A two-stage-priority rule based algorithm for robust resource-constrained project scheduling. Comput. Indust. Engin. 12 (2008).
- [25] N. Chistophides and C.A. Whitlock, Network synthesis with connectivity constraint : a survey. Oper. Res. (1981) 705–723. Zbl0473.90036
- [26] J. Coelho and L. Tavares, Comparative analysis of metaheuricstics for the resource constrained project scheduling problem. Technical report, Department of Civil Engineering, Instituto Superior Tecnico, Portugal (2003).
- [27] G. Dahl and M. Stoer, A polyhedral approach to multicommodity survivable network design. Numerische Math.68 (1994) 149–167. Zbl0809.65068MR1278454
- [28] J. Damay, Techniques de resolution basées sur la programmation linéaire pour l’ordonnancement de projet. PH.D. Thesis, Université de CLERMONT-FERRAND (2005).
- [29] J. Damay, A. Quilliot and E. Sanlaville, Linear programming based algorithms for preemptive and non preemptive RCPSP. EJOR 182 1012–1022. (2007). Zbl1121.90055
- [30] S. Demassey, C. Artigue and P. Michelon, Constraint–propagation-based cutting planes : an application to the resource-constrained-project-scheduling problem. INFORMS J. Comput. 17 (2005) 1. Zbl1239.90062MR2129806
- [31] E. Demeulemeester and W. Herroelen, New benchmark results for the multiple RCPSP. Manage. Sci.43 (1997) 1485–1492. Zbl0914.90160
- [32] B. De Reyck and W. Herroelen, A branch and bound procedure for the resource-constrained project scheduling problem with generalized precedence relations. EJOR111 (1998) 152–174. Zbl0948.90077
- [33] K. Djellab, Scheduling preemptive jobs with precedence constraints on parallel machines. EJOR117 (1999) 355-367. Zbl0998.90033
- [34] D. Dolev and M.K. Warmuth, Scheduling DAGs of bounded heights. J. Algor.5 (1984) 48–59. Zbl0547.68037MR736927
- [35] D. Debels, B. De Reyck, R. Leus, M. Vanhoucke, A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. EJOR169 (2006) 638–653. Zbl1079.90051MR2172364
- [36] B. Dushnik and W. Miller, Partially ordered sets. Amer. J. Math.63 (1941) 600–610. Zbl0025.31002MR4862JFM67.0157.01
- [37] P. Fortemps and M. Hapke, On the disjunctive graph for project scheduling. Foundat. Comput. Decis. Sci.22 (1997) 195–209. Zbl0902.90097
- [38] D.R. Fulkerson and J.R. Gross, Incidence matrices and interval graphs. Pac. J. Maths15 (1965) 835–855. Zbl0132.21001MR186421
- [39] R.L. Grahamson, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnoy-Khan, Optimization and approximation in deterministic scheduling : a survey. Annal. Disc. Math.5 (1979) 287–326. Zbl0411.90044MR558574
- [40] S. Hartmann and D. Briskorn, A survey of variants and extensions of the resource-constrained project scheduling problem. Europ. J. Operat. Res.207 (2010) 1–14. Zbl1205.90123MR2659413
- [41] W. Herroelen, E. Demeulemeester and B. de Reyck, A classification scheme for project scheduling, in Project Scheduling : recent models, algorithms and applications. Kluwer Acad Publishers (1999) 1–26.
- [42] W. Herroelen, Project Scheduling-Theory and Practice. Prod. Oper. Manag.14 (2006) 413–432.
- [43] M. Haouari, A. Gharbi, A improved max-flow based lower bound for minimizing maximum lateness on identical parallele machines. Operat. Res. Lett.31 (2003) 49–52 . Zbl1013.90066MR1946734
- [44] J. Josefowska, M. Mika, R. Rozycki, G. Waligora, J. Weglarcz, An almost optimal heuristic for preemptive Cmax scheduling of dependant task on parallel identical machines. Annal. OR129 (2004) 205–216. Zbl1056.90033MR2072299
- [45] R. Kolisch and A. Drexl, Adaptive search for solving hard project scheduling problems. Naval Res. Logist.43 (1996) 23–40. Zbl0870.90069
- [46] R. Kolisch and S. Hartmann, Experimental investigation of heuristics for the resource constrained scheduling problem : an update. EJOR174 (2006) 23–37. Zbl1116.90047
- [47] A. Kimms, Mathematical programming and financial objectives for scheduling projects. Oper. Res. Manag. Sci. Kluwer Academic Publisher (2001).
- [48] R. Kolisch, A. Sprecher and A. Drexel, Characterization and generation of a general class of resource constrained project scheduling problems. Manag. Sci.41 (1995) 1693–1703. Zbl0870.90070
- [49] R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisited : Theory and computation. Eur. J. Oper. Res.90 (1996) 320–333. Zbl0916.90151
- [50] R. Kolisch, R. Padman. An integrated survey of deterministic project scheduling. Omega48 (1999) 249–272.
- [51] R. Kolisch and S. Hartmann, Heuristic algorithms for solving the resource-constrained project scheduling problem : classification and computational analysis, in edited by J. Weglarcz. Project Scheduling : recent models, algorithms and applications, Kluwer Acad Press (1999).
- [52] Y. Kochetov and A. Stolyar, Evolutionnary local search with variable neighbourhood for the resource constrained scheduling problem, in Proc. 3 th int. Conf. Computer Sciences and Information Technologies, Russia (2003).
- [53] E.L. Lawler, K.J. Lenstra, A.H.G. Rinnoy-Kan and D.B. Schmoys, Sequencing and scheduling : algorithms and complexity, in Handbook of Operation Research and Management Sciences, Vol 4 : Logistics of Production and Inventory, edited by S. C. GRAVES, A.H.G. Rinnoy-kan, P.H. Zipkin. North-Holland (1993) 445–522. Zbl0557.90044
- [54] R. Leus and W. Herroelen, Stability and resource allocation in project planning. IIE transactions. 36 (2004) 1–16.
- [55] V.J. Leon and B. Ramamoorthy, Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling. OR Spektrum17 (1995) 173–182. Zbl0842.90062
- [56] A. Mingozzi, V. Maniezzo, S. Ricciardelli and L. Bianco, An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Manage. Sci.44 (1998) 714–729. Zbl1004.90036
- [57] M. Minoux, Network synthesis and optimum network design problems : models, solution methods and application. Networks19 (1989) 313–360. Zbl0666.90032MR996586
- [58] P.B. Mirchandani and R.L. Francis, Discrete location theory. John Wiley and sons (1990). Zbl0718.00021MR1066256
- [59] R.H. Mohring and F.J. Rademacher, Scheduling problems with resource duration interactions. Methods Oper. Res.48 (1984) 423–452. Zbl0561.90048
- [60] A. Moukrim and A. Quilliot, Optimal preemptive scheduling on a fixed number of identical parallel machines. Oper. Res. Lett.33 (2005) 143–151. Zbl1099.90022MR2101047
- [61] A. Moukrim and A. Quilliot, A relation between multiprocessor scheduling and linear programming. Order14 (1997) 269–278. Zbl0912.90178MR1634914
- [62] R.R. Muntz and E.G. Coffman, Preemptive scheduling of real time tasks on multiprocessor systems. J. ACM17 (1970) 324–338. Zbl0216.49702MR282644
- [63] K. Neumann, C. Schwindt and J. Zimmermann, Project scheduling with time windows and scarce resources. Springer, Berlin (2003). Zbl1059.90001MR2027537
- [64] K. Nonobe and T. Ibaraki, Formulation and tabu search algorithm for the resource constrained project scheduling problem. In C.C. Ribeiro and P. Hansen, editors, Essays and surveys in metaheuristics. Kluwer Academic Publishers, Dordrecht (2002) 557–588. Zbl1048.90116MR1866584
- [65] M. Palpant, C. Artigues and P. Michelon, LSSPER : solving the resource-constrained project scheduling problem with large neighbourhood search. Ann. Oper. Res.131 (2004) 237–257. Zbl1066.90037MR2095806
- [66] C.H. Papadimitriou and M. Yannanakis, Scheduling interval ordered tasks. SIAM J. Comput.8 (1979) 405–409. Zbl0421.68040MR539257
- [67] P.M. Pardalos and D.Z. Du, Network design : connectivity and facility location. DIMACS Series 40, N.Y, American Math Society (1998). Zbl0897.90099MR1612993
- [68] J.H. Patterson, A comparizon of exact approaches for solving the multiple constrained resource project scheduling problem. Manag. Sci.30 (1984) 854–867.
- [69] N. Sauer and M.G. Stone, Rational preemptive scheduling. Order4 (1987) 195–206. Zbl0648.68044MR916495
- [70] N. Sauer and M.G. Stone, Preemptive scheduling of interval orders is polynomial. Order5 (1989) 345–348. Zbl0699.68049MR1010383
- [71] A. Schirmer, Case-based reasoning and improved adaptive search for project scheduling. Naval Res. Logist.47 (2000) 201–222. Zbl0956.90011MR1745716
- [72] S.S. Liu and C.J. Wang, Resource-constrained construction project scheduling model for profit maximization considering cash flow. Automat. Constr.17 (2008) 966–974.
- [73] P. Tormos and A. Lova, Project scheduling with time varying resource constraints. Int. J. Prod. Res.38 (2000) 3937–3952. Zbl1094.90558
- [74] P. Tormos and A. Lova, A competitive heuristic solution technique for resource-constrained project scheduling. Ann. Oper. Res.102 (2001) 65–81. Zbl1024.90045MR1854419
- [75] P. Tormos and A. Lova, An efficient multi-pass heuristic for project scheduling with constrained resources. Int. J. Prod. Res.41 (2003) 1071–1086. Zbl1038.90038
- [76] P. Tormos and A. Lova, Integrating heuristics for resource constrained project scheduling : One step forward. Technical report, Department of Statistics and Operations Research, University of Valencia (2003). Zbl1038.90038
- [77] V. Valls, F. Ballestin and S. Quintanilla, A hybrid genetic algorithm for the RCPSP. Technical report, Department of Statistics and Operations Research, University of Valencia (2003). Zbl1032.90011
- [78] V. Valls, B. Ballestin and S. Quintanilla, Justification and RCPSP : a technique that pays. EJOR165 (2005) 375–386. Zbl1066.90045
- [79] P. Van Hentenryk, Constraint Programming. North Holland (1997).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.