Flow Polyhedra and Resource Constrained Project Scheduling Problems

 Access to full text

1. [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. [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. [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. [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. [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. [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. [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. [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. [9] K.R. Baker, Introduction to sequencing and scheduling. Wiley, N.Y (1974). 
10. [10] P. Baptiste, Resource constraints for preemptive and non preemptive scheduling, MSC Thesis, University PARIS VI (1995). 
11. [11] P. Baptiste and S. Demassey, Tight LP-bounds for resource constrained project scheduling. OR Spectrum26 (2004) 251–262. Zbl1072.90012
12. [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. [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. [14] C. Berge, Graphes et Hypergraphes. Dunod Ed (1975). Zbl0213.25702MR357173
15. [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. [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. [17] C. Briand, A new any-order schedule generation scheme for resource-constrained project scheduling. RAIRO - Oper. Res. (2009) 297–308. Zbl1170.90007MR2567990
18. [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. [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. [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. [21] J. Carlier and P. Chrétienne. Problèmes d’ordonnancements : modélisation, complexité et algorithmes. Masson Ed, Paris (1988). Zbl0774.90043
22. [22] J. Carlier and E. Neron, Computing redundant resources for the resource constrained project scheduling problem. EJOR176 (2007) 1452–1463. Zbl1104.90018MR2270857
23. [23] J. Carlier and E. Neron, On linear lower bounds for the resource constrained project scheduling problem. EJOR149 (2003) 314–324. Zbl1040.90017MR1993135
24. [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. [25] N. Chistophides and C.A. Whitlock, Network synthesis with connectivity constraint : a survey. Oper. Res. (1981) 705–723. Zbl0473.90036
26. [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. [27] G. Dahl and M. Stoer, A polyhedral approach to multicommodity survivable network design. Numerische Math.68 (1994) 149–167. Zbl0809.65068MR1278454
28. [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. [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. [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. [31] E. Demeulemeester and W. Herroelen, New benchmark results for the multiple RCPSP. Manage. Sci.43 (1997) 1485–1492. Zbl0914.90160
32. [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. [33] K. Djellab, Scheduling preemptive jobs with precedence constraints on parallel machines. EJOR117 (1999) 355-367. Zbl0998.90033
34. [34] D. Dolev and M.K. Warmuth, Scheduling DAGs of bounded heights. J. Algor.5 (1984) 48–59. Zbl0547.68037MR736927
35. [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. [36] B. Dushnik and W. Miller, Partially ordered sets. Amer. J. Math.63 (1941) 600–610. Zbl0025.31002MR4862JFM67.0157.01
37. [37] P. Fortemps and M. Hapke, On the disjunctive graph for project scheduling. Foundat. Comput. Decis. Sci.22 (1997) 195–209. Zbl0902.90097
38. [38] D.R. Fulkerson and J.R. Gross, Incidence matrices and interval graphs. Pac. J. Maths15 (1965) 835–855. Zbl0132.21001MR186421
39. [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. [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. [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. [42] W. Herroelen, Project Scheduling-Theory and Practice. Prod. Oper. Manag.14 (2006) 413–432. 
43. [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. [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. [45] R. Kolisch and A. Drexl, Adaptive search for solving hard project scheduling problems. Naval Res. Logist.43 (1996) 23–40. Zbl0870.90069
46. [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. [47] A. Kimms, Mathematical programming and financial objectives for scheduling projects. Oper. Res. Manag. Sci. Kluwer Academic Publisher (2001). 
48. [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. [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. [50] R. Kolisch, R. Padman. An integrated survey of deterministic project scheduling. Omega48 (1999) 249–272. 
51. [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. [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. [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. [54] R. Leus and W. Herroelen, Stability and resource allocation in project planning. IIE transactions. 36 (2004) 1–16. 
55. [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. [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. [57] M. Minoux, Network synthesis and optimum network design problems : models, solution methods and application. Networks19 (1989) 313–360. Zbl0666.90032MR996586
58. [58] P.B. Mirchandani and R.L. Francis, Discrete location theory. John Wiley and sons (1990). Zbl0718.00021MR1066256
59. [59] R.H. Mohring and F.J. Rademacher, Scheduling problems with resource duration interactions. Methods Oper. Res.48 (1984) 423–452. Zbl0561.90048
60. [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. [61] A. Moukrim and A. Quilliot, A relation between multiprocessor scheduling and linear programming. Order14 (1997) 269–278. Zbl0912.90178MR1634914
62. [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. [63] K. Neumann, C. Schwindt and J. Zimmermann, Project scheduling with time windows and scarce resources. Springer, Berlin (2003). Zbl1059.90001MR2027537
64. [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. [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. [66] C.H. Papadimitriou and M. Yannanakis, Scheduling interval ordered tasks. SIAM J. Comput.8 (1979) 405–409. Zbl0421.68040MR539257
67. [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. [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. [69] N. Sauer and M.G. Stone, Rational preemptive scheduling. Order4 (1987) 195–206. Zbl0648.68044MR916495
70. [70] N. Sauer and M.G. Stone, Preemptive scheduling of interval orders is polynomial. Order5 (1989) 345–348. Zbl0699.68049MR1010383
71. [71] A. Schirmer, Case-based reasoning and improved adaptive search for project scheduling. Naval Res. Logist.47 (2000) 201–222. Zbl0956.90011MR1745716
72. [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. [73] P. Tormos and A. Lova, Project scheduling with time varying resource constraints. Int. J. Prod. Res.38 (2000) 3937–3952. Zbl1094.90558
74. [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. [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. [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. [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. [78] V. Valls, B. Ballestin and S. Quintanilla, Justification and RCPSP : a technique that pays. EJOR165 (2005) 375–386. Zbl1066.90045
79. [79] P. Van Hentenryk, Constraint Programming. North Holland (1997).