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.
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] , and , Bi-objective resource-constrained project scheduling with robustness and makespan criteria. Appl. Math. Comput. 180 (2006) 146-152. | MR | Zbl
[2] , , and , Applications of network optimization, in Network Models (Chapter 1). Handbooks Oper. Res. Manage. Sci. 7 (1995) 1-83. | MR | Zbl
[3] , and . Network flows : theory, algorithms and applications. Prentice hall, Englewood Cliffs, N.J (1993). | MR | Zbl
[4] and , A robust genetic algorithm for resource allocation in project scheduling. Ann. Oper. Res. 102 (2001) 83-109. | MR | Zbl
[5] , and , Improving the performance of genetic algorithms for the RCPSP problem, in Proc. 9th Int. workshop on project management and scheduling (2004) 40-43.
[6] and , A polynomial activity insertion algorithm in a multiresource schedule with cumulative constraints and multiple nodes. EJOR 127 (2000) 297-316. | Zbl
[7] , and , Insertion techniques for static and dynamic resource constrained project scheduling. EJOR 149 (2003) 249-267. | MR | Zbl
[8] and , The resource-constrained activity insertion problem with minimum and maximum time lags. J. Schedul. 12 (2009) 447-460. | MR | Zbl
[9] , Introduction to sequencing and scheduling. Wiley, N.Y (1974).
[10] , Resource constraints for preemptive and non preemptive scheduling, MSC Thesis, University PARIS VI (1995).
[11] and , Tight LP-bounds for resource constrained project scheduling. OR Spectrum 26 (2004) 251-262. | Zbl
[12] , , and , Constraint-based scheduling and planning, in Handbook of Constraint Programming 22, edited by F. Rossi, P. Van Beek. Elsevier (2006) 759-798. | Zbl
[13] , and , 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] , Graphes et Hypergraphes. Dunod Ed (1975). | MR | Zbl
[15] , , and , Scheduling in computer and manufacturing systems. 2th edn, Springer-Verlag, Berlin (1993). | Zbl
[16] and , 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] , A new any-order schedule generation scheme for resource-constrained project scheduling. RAIRO - Oper. Res. (2009) 297-308. | Numdam | MR | Zbl
[18] and , A linear programming and constraint propagation based lower bound for the RCPSP. EJOR 127 (2000) 355-362. | Zbl
[19] , , and , A branch and bound algorithm for the resource constrained project scheduling problem. EJOR 107 (1998) 272-288. | Zbl
[20] , , , and , Resource-constrained project scheduling : notation, classification, models and methods. EJOR 112 (1999) 3-41. | Zbl
[21] and . Problèmes d'ordonnancements : modélisation, complexité et algorithmes. Masson Ed, Paris (1988). | Zbl
[22] and , Computing redundant resources for the resource constrained project scheduling problem. EJOR 176 (2007) 1452-1463. | MR | Zbl
[23] and , On linear lower bounds for the resource constrained project scheduling problem. EJOR 149 (2003) 314-324. | MR | Zbl
[24] and , A two-stage-priority rule based algorithm for robust resource-constrained project scheduling. Comput. Indust. Engin. 12 (2008).
[25] and , Network synthesis with connectivity constraint : a survey. Oper. Res. (1981) 705-723. | Zbl
[26] and , Comparative analysis of metaheuricstics for the resource constrained project scheduling problem. Technical report, Department of Civil Engineering, Instituto Superior Tecnico, Portugal (2003).
[27] and , A polyhedral approach to multicommodity survivable network design. Numerische Math. 68 (1994) 149-167. | MR | Zbl
[28] , Techniques de resolution basées sur la programmation linéaire pour l'ordonnancement de projet. PH.D. Thesis, Université de CLERMONT-FERRAND (2005).
[29] , and , Linear programming based algorithms for preemptive and non preemptive RCPSP. EJOR 182 1012-1022. (2007). | Zbl
[30] , and , Constraint-propagation-based cutting planes : an application to the resource-constrained-project-scheduling problem. INFORMS J. Comput. 17 (2005) 1. | MR | Zbl
[31] and , New benchmark results for the multiple RCPSP. Manage. Sci. 43 (1997) 1485-1492. | Zbl
[32] and , A branch and bound procedure for the resource-constrained project scheduling problem with generalized precedence relations. EJOR 111 (1998) 152-174. | Zbl
[33] , Scheduling preemptive jobs with precedence constraints on parallel machines. EJOR 117 (1999) 355-367. | Zbl
[34] and , Scheduling DAGs of bounded heights. J. Algor. 5 (1984) 48-59. | MR | Zbl
[35] , , , , A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. EJOR 169 (2006) 638-653. | MR | Zbl
[36] and , Partially ordered sets. Amer. J. Math. 63 (1941) 600-610. | JFM | MR
[37] and , On the disjunctive graph for project scheduling. Foundat. Comput. Decis. Sci. 22 (1997) 195-209. | Zbl
[38] and , Incidence matrices and interval graphs. Pac. J. Maths 15 (1965) 835-855. | MR | Zbl
[39] , , and , Optimization and approximation in deterministic scheduling : a survey. Annal. Disc. Math. 5 (1979) 287-326. | MR | Zbl
[40] and , A survey of variants and extensions of the resource-constrained project scheduling problem. Europ. J. Operat. Res. 207 (2010) 1-14. | MR | Zbl
[41] , and , A classification scheme for project scheduling, in Project Scheduling : recent models, algorithms and applications. Kluwer Acad Publishers (1999) 1-26.
[42] , Project Scheduling-Theory and Practice. Prod. Oper. Manag. 14 (2006) 413-432.
[43] , , 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] , , , , , An almost optimal heuristic for preemptive Cmax scheduling of dependant task on parallel identical machines. Annal. OR 129 (2004) 205-216. | MR | Zbl
[45] and , Adaptive search for solving hard project scheduling problems. Naval Res. Logist. 43 (1996) 23-40. | Zbl
[46] and , Experimental investigation of heuristics for the resource constrained scheduling problem : an update. EJOR 174 (2006) 23-37. | Zbl
[47] , Mathematical programming and financial objectives for scheduling projects. Oper. Res. Manag. Sci. Kluwer Academic Publisher (2001).
[48] , and , Characterization and generation of a general class of resource constrained project scheduling problems. Manag. Sci. 41 (1995) 1693-1703. | Zbl
[49] , Serial and parallel resource-constrained project scheduling methods revisited : Theory and computation. Eur. J. Oper. Res. 90 (1996) 320-333. | Zbl
[50] , . An integrated survey of deterministic project scheduling. Omega 48 (1999) 249-272.
[51] and , 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] and , 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] , , and , 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] and , Stability and resource allocation in project planning. IIE transactions. 36 (2004) 1-16.
[55] and , Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling. OR Spektrum 17 (1995) 173-182. | Zbl
[56] , , and , An exact algorithm for project scheduling with resource constraints based on a new mathematical formulation. Manage. Sci. 44 (1998) 714-729. | Zbl
[57] , Network synthesis and optimum network design problems : models, solution methods and application. Networks 19 (1989) 313-360. | MR | Zbl
[58] and , Discrete location theory. John Wiley and sons (1990). | MR | Zbl
[59] and , Scheduling problems with resource duration interactions. Methods Oper. Res. 48 (1984) 423-452. | Zbl
[60] and , Optimal preemptive scheduling on a fixed number of identical parallel machines. Oper. Res. Lett. 33 (2005) 143-151. | MR | Zbl
[61] and , A relation between multiprocessor scheduling and linear programming. Order 14 (1997) 269-278. | MR | Zbl
[62] and , Preemptive scheduling of real time tasks on multiprocessor systems. J. ACM 17 (1970) 324-338. | MR | Zbl
[63] , and , Project scheduling with time windows and scarce resources. Springer, Berlin (2003). | MR | Zbl
[64] and , 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] , and , LSSPER : solving the resource-constrained project scheduling problem with large neighbourhood search. Ann. Oper. Res. 131 (2004) 237-257. | MR | Zbl
[66] and , Scheduling interval ordered tasks. SIAM J. Comput. 8 (1979) 405-409. | MR | Zbl
[67] and , Network design : connectivity and facility location. DIMACS Series 40, N.Y, American Math Society (1998). | MR | Zbl
[68] , A comparizon of exact approaches for solving the multiple constrained resource project scheduling problem. Manag. Sci. 30 (1984) 854-867.
[69] and , Rational preemptive scheduling. Order 4 (1987) 195-206. | MR | Zbl
[70] and , Preemptive scheduling of interval orders is polynomial. Order 5 (1989) 345-348. | MR | Zbl
[71] , Case-based reasoning and improved adaptive search for project scheduling. Naval Res. Logist. 47 (2000) 201-222. | MR | Zbl
[72] and , Resource-constrained construction project scheduling model for profit maximization considering cash flow. Automat. Constr. 17 (2008) 966-974.
[73] and , Project scheduling with time varying resource constraints. Int. J. Prod. Res. 38 (2000) 3937-3952. | Zbl
[74] and , A competitive heuristic solution technique for resource-constrained project scheduling. Ann. Oper. Res. 102 (2001) 65-81. | MR | Zbl
[75] and , An efficient multi-pass heuristic for project scheduling with constrained resources. Int. J. Prod. Res. 41 (2003) 1071-1086. | Zbl
[76] and , Integrating heuristics for resource constrained project scheduling : One step forward. Technical report, Department of Statistics and Operations Research, University of Valencia (2003).
[77] , and , A hybrid genetic algorithm for the RCPSP. Technical report, Department of Statistics and Operations Research, University of Valencia (2003).
[78] , and , Justification and RCPSP : a technique that pays. EJOR 165 (2005) 375-386. | Zbl
[79] , Constraint Programming. North Holland (1997).
Cité par Sources :
