Flow Polyhedra and Resource Constrained Project Scheduling Problems
RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 4, pp. 373-409.

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.

DOI : 10.1051/ro/2012021
Classification : 90-08
Mots clés : scheduling with resource constraints, network flow theory
@article{RO_2012__46_4_373_0,
     author = {Quilliot, Alain and Toussaint, H\'el\`ene},
     title = {Flow {Polyhedra} and {Resource} {Constrained} {Project} {Scheduling} {Problems}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {373--409},
     publisher = {EDP-Sciences},
     volume = {46},
     number = {4},
     year = {2012},
     doi = {10.1051/ro/2012021},
     mrnumber = {3029896},
     zbl = {1262.90068},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2012021/}
}
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
SP  - 373
EP  - 409
VL  - 46
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2012021/
DO  - 10.1051/ro/2012021
LA  - en
ID  - RO_2012__46_4_373_0
ER  - 
%0 Journal Article
%A Quilliot, Alain
%A Toussaint, Hélène
%T Flow Polyhedra and Resource Constrained Project Scheduling Problems
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2012
%P 373-409
%V 46
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2012021/
%R 10.1051/ro/2012021
%G en
%F RO_2012__46_4_373_0
Quilliot, Alain; Toussaint, Hélène. Flow Polyhedra and Resource Constrained Project Scheduling Problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 46 (2012) no. 4, pp. 373-409. doi : 10.1051/ro/2012021. http://www.numdam.org/articles/10.1051/ro/2012021/

[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. | MR | Zbl

[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. | MR | Zbl

[3] R.V. Ahuja, T.L. Magnanti and J.B. Orlin. Network flows : theory, algorithms and applications. Prentice hall, Englewood Cliffs, N.J (1993). | MR | Zbl

[4] J. Alcaraz and C. Maroto, A robust genetic algorithm for resource allocation in project scheduling. Ann. Oper. Res. 102 (2001) 83-109. | MR | Zbl

[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. EJOR 127 (2000) 297-316. | Zbl

[7] C. Artigues, P. Michelon and S. Reusser, Insertion techniques for static and dynamic resource constrained project scheduling. EJOR 149 (2003) 249-267. | MR | Zbl

[8] C. Artigues and C. Briand, The resource-constrained activity insertion problem with minimum and maximum time lags. J. Schedul. 12 (2009) 447-460. | MR | Zbl

[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 Spectrum 26 (2004) 251-262. | Zbl

[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. | Zbl

[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. | MR | Zbl

[14] C. Berge, Graphes et Hypergraphes. Dunod Ed (1975). | MR | Zbl

[15] J. Blazewiecz, K.H. Ecker, G. Schmlidt and J. Weglarcz, Scheduling in computer and manufacturing systems. 2th edn, Springer-Verlag, Berlin (1993). | Zbl

[16] K. Bouleimen and H. Lecocq, A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. EJOR 149 (2003) 268-281. | MR | Zbl

[17] C. Briand, A new any-order schedule generation scheme for resource-constrained project scheduling. RAIRO - Oper. Res. (2009) 297-308. | Numdam | MR | Zbl

[18] P. Brucker and S. Knust, A linear programming and constraint propagation based lower bound for the RCPSP. EJOR 127 (2000) 355-362. | Zbl

[19] P. Brucker, S. Knust, A. Schoo and O. Thiele, A branch and bound algorithm for the resource constrained project scheduling problem. EJOR 107 (1998) 272-288. | Zbl

[20] P. Brucker, A. Drexl, R. Mohring, K. Neumann and E. Pesch, Resource-constrained project scheduling : notation, classification, models and methods. EJOR 112 (1999) 3-41. | Zbl

[21] J. Carlier and P. Chrétienne. Problèmes d'ordonnancements : modélisation, complexité et algorithmes. Masson Ed, Paris (1988). | Zbl

[22] J. Carlier and E. Neron, Computing redundant resources for the resource constrained project scheduling problem. EJOR 176 (2007) 1452-1463. | MR | Zbl

[23] J. Carlier and E. Neron, On linear lower bounds for the resource constrained project scheduling problem. EJOR 149 (2003) 314-324. | MR | Zbl

[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. | Zbl

[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. | MR | Zbl

[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). | Zbl

[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. | MR | Zbl

[31] E. Demeulemeester and W. Herroelen, New benchmark results for the multiple RCPSP. Manage. Sci. 43 (1997) 1485-1492. | Zbl

[32] B. De Reyck and W. Herroelen, A branch and bound procedure for the resource-constrained project scheduling problem with generalized precedence relations. EJOR 111 (1998) 152-174. | Zbl

[33] K. Djellab, Scheduling preemptive jobs with precedence constraints on parallel machines. EJOR 117 (1999) 355-367. | Zbl

[34] D. Dolev and M.K. Warmuth, Scheduling DAGs of bounded heights. J. Algor. 5 (1984) 48-59. | MR | Zbl

[35] D. Debels, B. De Reyck, R. Leus, M. Vanhoucke, A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. EJOR 169 (2006) 638-653. | MR | Zbl

[36] B. Dushnik and W. Miller, Partially ordered sets. Amer. J. Math. 63 (1941) 600-610. | JFM | MR

[37] P. Fortemps and M. Hapke, On the disjunctive graph for project scheduling. Foundat. Comput. Decis. Sci. 22 (1997) 195-209. | Zbl

[38] D.R. Fulkerson and J.R. Gross, Incidence matrices and interval graphs. Pac. J. Maths 15 (1965) 835-855. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[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 . | MR | Zbl

[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. OR 129 (2004) 205-216. | MR | Zbl

[45] R. Kolisch and A. Drexl, Adaptive search for solving hard project scheduling problems. Naval Res. Logist. 43 (1996) 23-40. | Zbl

[46] R. Kolisch and S. Hartmann, Experimental investigation of heuristics for the resource constrained scheduling problem : an update. EJOR 174 (2006) 23-37. | Zbl

[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. | Zbl

[49] R. Kolisch, Serial and parallel resource-constrained project scheduling methods revisited : Theory and computation. Eur. J. Oper. Res. 90 (1996) 320-333. | Zbl

[50] R. Kolisch, R. Padman. An integrated survey of deterministic project scheduling. Omega 48 (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. | Zbl

[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 Spektrum 17 (1995) 173-182. | Zbl

[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. | Zbl

[57] M. Minoux, Network synthesis and optimum network design problems : models, solution methods and application. Networks 19 (1989) 313-360. | MR | Zbl

[58] P.B. Mirchandani and R.L. Francis, Discrete location theory. John Wiley and sons (1990). | MR | Zbl

[59] R.H. Mohring and F.J. Rademacher, Scheduling problems with resource duration interactions. Methods Oper. Res. 48 (1984) 423-452. | Zbl

[60] A. Moukrim and A. Quilliot, Optimal preemptive scheduling on a fixed number of identical parallel machines. Oper. Res. Lett. 33 (2005) 143-151. | MR | Zbl

[61] A. Moukrim and A. Quilliot, A relation between multiprocessor scheduling and linear programming. Order 14 (1997) 269-278. | MR | Zbl

[62] R.R. Muntz and E.G. Coffman, Preemptive scheduling of real time tasks on multiprocessor systems. J. ACM 17 (1970) 324-338. | MR | Zbl

[63] K. Neumann, C. Schwindt and J. Zimmermann, Project scheduling with time windows and scarce resources. Springer, Berlin (2003). | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[66] C.H. Papadimitriou and M. Yannanakis, Scheduling interval ordered tasks. SIAM J. Comput. 8 (1979) 405-409. | MR | Zbl

[67] P.M. Pardalos and D.Z. Du, Network design : connectivity and facility location. DIMACS Series 40, N.Y, American Math Society (1998). | MR | Zbl

[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. Order 4 (1987) 195-206. | MR | Zbl

[70] N. Sauer and M.G. Stone, Preemptive scheduling of interval orders is polynomial. Order 5 (1989) 345-348. | MR | Zbl

[71] A. Schirmer, Case-based reasoning and improved adaptive search for project scheduling. Naval Res. Logist. 47 (2000) 201-222. | MR | Zbl

[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. | Zbl

[74] P. Tormos and A. Lova, A competitive heuristic solution technique for resource-constrained project scheduling. Ann. Oper. Res. 102 (2001) 65-81. | MR | Zbl

[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. | Zbl

[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).

[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).

[78] V. Valls, B. Ballestin and S. Quintanilla, Justification and RCPSP : a technique that pays. EJOR 165 (2005) 375-386. | Zbl

[79] P. Van Hentenryk, Constraint Programming. North Holland (1997).

Cité par Sources :