Resource–constrained Project Scheduling
Models, Algorithms, Extensions and Applications
Gebonden Engels 2008 9781848210349Samenvatting
This title presents a large variety of models and algorithms dedicated to the resource–constrained project scheduling problem (RCPSP), which aims at scheduling at minimal duration a set of activities subject to precedence constraints and limited resource availabilities.
In the first part, the standard variant of RCPSP is presented and analyzed as a combinatorial optimization problem. Constraint programming and integer linear programming formulations are given. Relaxations based on these formulations and also on related scheduling problems are presented. Exact methods and heuristics are surveyed. Computational experiments, aiming at providing an empirical insight on the difficulty of the problem, are provided.
The second part of the book focuses on several other variants of the RCPSP and on their solution methods. Each variant takes account of real–life characteristics which are not considered in the standard version, such as possible interruptions of activities, production and consumption of resources, cost–based approaches and uncertainty considerations.
The last part presents industrial case studies where the RCPSP plays a central part. Applications are presented in various domains such as assembly shop and rolling ingots production scheduling, project management in information technology companies and instruction scheduling for VLIW processor architectures.
Specificaties
Lezersrecensies
Inhoudsopgave
<p>Part 1. Models and Algorithms for the Standard Resource–Constrained</p>
<p>Project Scheduling Problem 19</p>
<p>Chapter 1. The Resource–Constrained Project Scheduling Problem 21<br /> Christian ARTIGUES</p>
<p>1.1. A combinatorial optimization problem 21</p>
<p>1.2. A simple resource–constrained project example 23</p>
<p>1.3. Computational complexity 23</p>
<p>1.4. Dominant and non–dominant schedule subsets 26</p>
<p>1.5. Order–based representation of schedules and related dominant schedule sets 28</p>
<p>1.6. Forbidden sets and resource flow network formulations of the RCPSP 31</p>
<p>1.7. A simple method for enumerating a dominant set of quasi–active schedules 34</p>
<p>Chapter 2. Resource and Precedence Constraint Relaxation 37<br /> Emmanuel NÉRON</p>
<p>2.1. Relaxing resource constraints 38</p>
<p>2.2. Calculating the disjunctive subproblem 38</p>
<p>2.3. Deducing identical parallel machine problems 41</p>
<p>2.4. Single cumulative resource problem 45</p>
<p>2.5. Conclusion and perspectives 47</p>
<p>Chapter 3. Mathematical Programming Formulations and Lower Bounds 49<br /> Sophie DEMASSEY</p>
<p>3.1. Sequence–based models 50</p>
<p>3.1.1. Minimal forbidden sets 51</p>
<p>3.1.2. Resource flow 52</p>
<p>3.2. Time–indexed formulations 53</p>
<p>3.2.1. Resource conflicts as linear constraints 54</p>
<p>3.2.2. Feasible configurations 56</p>
<p>3.2.2.1. Combinatorial relaxations 58</p>
<p>3.2.2.2. Column generation and further improvements 59</p>
<p>3.2.2.3. Cutting planes for the preemptive relaxation 60</p>
<p>3.3. Linear lower bounds and redundant resources 61</p>
<p>Chapter 4. Constraint Programming Formulations and Propagation Algorithms 63<br /> Philippe LABORIE and Wim NUIJTEN</p>
<p>4.1. Constraint formulations 63</p>
<p>4.1.1. Constraint programming 63</p>
<p>4.1.2. Constraint–based scheduling 64</p>
<p>4.2. Constraint propagation algorithms 65</p>
<p>4.2.1. Temporal constraints 65</p>
<p>4.2.2. Timetabling 66</p>
<p>4.2.3. Disjunctive reasoning 67</p>
<p>4.2.4. Edge–finding 67</p>
<p>4.2.5. Energy reasoning 68</p>
<p>4.2.6. Precedence graph 70</p>
<p>4.2.7. Energy precedence 70</p>
<p>4.2.8. Balance constraint 71</p>
<p>4.3. Conclusion 72</p>
<p>Chapter 5. Branching Schemes for Branch–and–Bound 73<br /> Emmanuel NÉRON</p>
<p>5.1. Chronological branching scheme 75</p>
<p>5.1.1. Adding one activity to a partial solution 75</p>
<p>5.1.1.1. Considering all relevant activities 75</p>
<p>5.1.1.2. Delaying one activity 77</p>
<p>5.1.2. Dominance rule: left shift and global left shift 78</p>
<p>5.1.3. Adding a subset of activities to a partial solution 79</p>
<p>5.1.3.1. Delaying alternatives 79</p>
<p>5.1.3.2. Building a solution using blocks 80</p>
<p>5.1.4. Dominance rule: cut–set 81</p>
<p>5.2. Specific branching schemes 82</p>
<p>5.2.1. Fixing disjunction and parallel relationship 82</p>
<p>5.2.2. Reducing time–windows of activities 83</p>
<p>5.2.3. Resolving forbidden sets 84</p>
<p>5.3. Conclusion and perspectives 85</p>
<p>Chapter 6. Heuristics 87<br /> Christian ARTIGUES and David RIVREAU</p>
<p>6.1. Schedule representation schemes 87</p>
<p>6.1.1.Natural date variables 87</p>
<p>6.1.2. List schedule generation scheme representations 88</p>
<p>6.1.3. Set–based representations 88</p>
<p>6.1.4.Resource flow network representation 89</p>
<p>6.2. Constructive heuristics 89</p>
<p>6.2.1. Standard list schedule generation scheme heuristics 89</p>
<p>6.2.2. A generic insertion–based list schedule generation scheme 91</p>
<p>6.2.3. Set schedule generation scheme heuristics 93</p>
<p>6.2.4. (Double–) justification–based methods 94</p>
<p>6.3. Local search neighborhoods 94</p>
<p>6.3.1. List–based neighborhoods 95</p>
<p>6.3.2. Set–based neighborhoods 95</p>
<p>6.3.3. Resource flow–based neighborhoods 96</p>
<p>6.3.4. Extended neighborhood for natural date variables 96</p>
<p>6.4. Metaheuristics 97</p>
<p>6.4.1. Simulated annealing 97</p>
<p>6.4.2. Tabu search 97</p>
<p>6.4.3. Population–based metaheuristics 98</p>
<p>6.4.4. Additional methods 99</p>
<p>6.5. Conclusion 100</p>
<p>6.6. Appendix 101</p>
<p>6.6.1. Serial list schedule generation revisited 101</p>
<p>6.6.2. Parallel list schedule generation revisited 104</p>
<p>Chapter 7. Benchmark Instance Indicators and Computational Comparison of Methods 107<br /> Christian ARTIGUES, Oumar KONÉ, Pierre LOPEZ, Marcel MONGEAU, Emmanuel NÉRON and David RIVREAU</p>
<p>7.1. Introduction 107</p>
<p>7.2. Standard instance indicators 108</p>
<p>7.3. New instance indicators 112</p>
<p>7.4. State–of–the–art benchmark instances 114</p>
<p>7.5. A critical analysis of the instance indicators 118</p>
<p>7.5.1. Indicator comparison between trivial and non–trivial instances 118</p>
<p>7.5.2. Indicator stability and correlation 120</p>
<p>7.6. Comparison of solution methods 124</p>
<p>7.6.1. Selected methods and experimental framework 124</p>
<p>7.6.2. Results on the KSD30 instances 129</p>
<p>7.6.3. Results on the BL instances 131</p>
<p>7.6.4. Results on the KSD60 instances 132</p>
<p>7.6.5. Results on the Pack instances 134</p>
<p>7.7. Conclusion 135</p>
<p>Part 2. Variants and Extensions 137</p>
<p>Chapter 8. Preemptive Activities 139<br /> Jean DAMAY</p>
<p>8.1. Preemption in scheduling 139</p>
<p>8.2. State of the art 140</p>
<p>8.2.1. Integral preemption for the RCPSP 140</p>
<p>8.2.2. Rational preemption for parallel machine scheduling problems 141</p>
<p>8.3. Recent LP–based methods 142</p>
<p>8.3.1. Reformulation 142</p>
<p>8.3.2. A specific neighborhood search algorithm 144</p>
<p>8.3.2.1. Descent approach 144</p>
<p>8.3.2.2. Diversification techniques 145</p>
<p>8.3.2.3. Experimental results 145</p>
<p>8.3.3. Exact methods 146</p>
<p>8.3.3.1. Branch–and–bound 146</p>
<p>8.3.3.2. Branch and cut and price 147</p>
<p>8.4. Conclusion 147</p>
<p>Chapter 9. Multi–Mode and Multi–Skill Project Scheduling Problem 149<br /> Odile BELLENGUEZ–MORINEAU and Emmanuel NÉRON</p>
<p>9.1. Introduction 149</p>
<p>9.2. Multi–Mode RCPSP 150</p>
<p>9.2.1. Problem presentation 150</p>
<p>9.2.2. Branching schemes for solving multi–mode RCPSP 152</p>
<p>9.2.3. Dominance rules 153</p>
<p>9.3. Multi–Skill Project Scheduling Problem 154</p>
<p>9.3.1. Problem presentation 154</p>
<p>9.3.2. Branching scheme based on time–windows reduction 157</p>
<p>9.3.3. Lower bounds and time–bound adjustments 158</p>
<p>9.3.4. Dominance rule 159</p>
<p>9.4. Conclusion and research directions 160</p>
<p>Chapter 10. Project Scheduling with Production and Consumption of Resources: How to Build Schedules 161<br /> Jacques CARLIER, AzizMOUKRIM and Huang XU</p>
<p>10.1. Introduction 161</p>
<p>10.2. The precedence–constrained project scheduling problem 162</p>
<p>10.2.1. Traditional precedence constraints 162</p>
<p>10.2.2. AND/OR precedence constraints 163</p>
<p>10.3. The resource–constrained project scheduling problem 164</p>
<p>10.3.1. Graph representation 164</p>
<p>10.3.2. The strict order algorithm 164</p>
<p>10.4. Scheduling problems with production and consumption of a non–renewable resource 166</p>
<p>10.5. Discussion 170</p>
<p>Chapter 11. Activity Insertion Problem in a RCPSP with Minimum and Maximum Time Lags 171<br /> Christian ARTIGUES and Cyril BRIAND</p>
<p>11.1. Introduction 171</p>
<p>11.2. Problem statement 172</p>
<p>11.3. Insertion positions 176</p>
<p>11.4. Feasibility conditions under a makespan upper bound 176</p>
<p>11.5. Computational complexity of the insertion problem with minimum and maximum time lags 178</p>
<p>11.6. A polynomial algorithm for the insertion problem with minimum time lags only 181</p>
<p>11.7. Conclusion 190</p>
<p>Chapter 12. Reactive Approaches 191<br /> Christelle GUÉRET and Narendra JUSSIEN</p>
<p>12.1. Dynamic project scheduling 191</p>
<p>12.2. Explanations and constraint programming for solving dynamic problems 192</p>
<p>12.2.1. Dynamic problems and constraint programming 192</p>
<p>12.2.2. Explanation–based constraint programming 193</p>
<p>12.3. An explanation–based approach for solving dynamic project scheduling 194</p>
<p>12.3.1. The tree search to solve static instances 195</p>
<p>12.3.2. Incrementally handling unexpected events 196</p>
<p>12.4. Experimental results 197</p>
<p>12.4.1. Stability measures 197</p>
<p>12.4.2. Test set 197</p>
<p>12.4.3. Computational results 198</p>
<p>12.4.3.1. Analysis of the results in terms of cpu time 199</p>
<p>12.4.3.2. Analysis of the stability 200</p>
<p>12.5. Conclusion 201</p>
<p>Chapter 13. Proactive–reactive Project Scheduling 203<br /> Erik DEMEULEMEESTER, Willy HERROELEN and Roel LEUS</p>
<p>13.1. Introduction 203</p>
<p>13.2. Solution robust scheduling under activity duration uncertainty 204</p>
<p>13.2.1. The proactive/reactive scheduling problem 204</p>
<p>13.2.2. Proactive scheduling 205</p>
<p>13.2.2.1.Robust resource allocation 205</p>
<p>13.2.2.2. Buffer insertion 206</p>
<p>13.2.3. Reactive scheduling 207</p>
<p>13.3. Solution robust scheduling under resource availability uncertainty 209</p>
<p>13.3.1. The problem 209</p>
<p>13.3.1.1. Proactive strategy 209</p>
<p>13.3.1.2. Reactive strategy 210</p>
<p>13.4. Conclusions and suggestions for further research 210</p>
<p>13.5. Acknowledgements 211</p>
<p>Chapter 14. RCPSP with Financial Costs 213<br /> Laure–Emmanuelle DREZET</p>
<p>14.1. Problem presentation and context 213</p>
<p>14.2. Definitions and notations 214</p>
<p>14.2.1. Definitions 214</p>
<p>14.2.2. Notations 215</p>
<p>14.2.3. Classification 216</p>
<p>14.3. NPV maximization 217</p>
<p>14.3.1. Unconstrained resources: MAXNPV and PSP 217</p>
<p>14.3.2. Constrained resources: RCPSPDC, CCPSP and PSP 219</p>
<p>14.4. Resource–related costs 221</p>
<p>14.4.1. Resource Leveling Problem 221</p>
<p>14.4.2. Resource Investment Problem (RIP) and Resource Renting Problem (RRP) 223</p>
<p>14.5. Conclusion 225</p>
<p>Part 3. Industrial Applications 227</p>
<p>Chapter 15. Assembly Shop Scheduling 229<br /> Michel GOURGAND, Nathalie GRANGEON and Sylvie NORRE</p>
<p>15.1. The assembly shop scheduling problem 229</p>
<p>15.1.1. Mono shop problem 230</p>
<p>15.1.1.1. Physical subsystem 230</p>
<p>15.1.1.2. Logical subsystem 230</p>
<p>15.1.1.3. Decisional subsystem 231</p>
<p>15.1.2. Multi shop problem 232</p>
<p>15.2. Link with the RCPSP 233</p>
<p>15.3. Proposition of extensions 234</p>
<p>15.3.1. RCPSP with variable demand profile 235</p>
<p>15.3.2. RCPSP with resource individualization 237</p>
<p>15.4. Proposition of solution methods 239</p>
<p>15.5. Some results 240</p>
<p>15.6. Conclusion 242</p>
<p>Chapter 16. Employee Scheduling in an IT Company 243<br /> Laure–Emmanuelle DREZET and Jean–Charles BILLAUT</p>
<p>16.1. Introduction 243</p>
<p>16.2. Problem presentation and context 244</p>
<p>16.3. Real life example 247</p>
<p>16.4. Predictive phase 250</p>
<p>16.4.1. Greedy algorithms 250</p>
<p>16.4.2. Tabu search algorithm 251</p>
<p>16.5. Proactive phase 251</p>
<p>16.6. Reactive phase 252</p>
<p>16.7. Computational experiments 253</p>
<p>16.7.1. Predictive and proactive algorithms 253</p>
<p>16.7.2. Reactive algorithm 254</p>
<p>16.8. Conclusion 254</p>
<p>Chapter 17. Rolling Ingots Production Scheduling 257<br /> Christoph SCHWINDT and Norbert TRAUTMANN</p>
<p>17.1. Introduction 257</p>
<p>17.2. Project scheduling model 259</p>
<p>17.2.1. Activities and temporal constraints 259</p>
<p>17.2.2. Resource constraints 261</p>
<p>17.2.3. Production scheduling problem 264</p>
<p>17.3. Solution method 264</p>
<p>17.4. Conclusions 266</p>
<p>Chapter 18. Resource–Constrained Modulo Scheduling 267<br /> Benoît DUPONT DE DINECHIN, Christian ARTIGUES and Sadia AZEM</p>
<p>18.1. Introduction 267</p>
<p>18.2. The resource–constrained modulo scheduling problem 268</p>
<p>18.2.1. The resource–constrained cyclic scheduling problem 268</p>
<p>18.2.2. The resource–constrained modulo scheduling problem 269</p>
<p>18.2.3. From modulo scheduling to software pipelining 270</p>
<p>18.3. Integer linear programming formulations 273</p>
<p>18.3.1. The RCMSP formulations by Eichenberger et al 273</p>
<p>18.3.2. A new time–indexed RCMSP formulation 274</p>
<p>18.4. Solving the RCMSP formulations 275</p>
<p>18.4.1. Reducing the size of the RCMSP formulations 275</p>
<p>18.4.2. A large neighborhood search for the RCMSP 275</p>
<p>18.4.3. Implementation and experiments 276</p>
<p>18.5. Summary and conclusions 277</p>
<p>Bibliography 279</p>
<p>List of Authors 303</p>
<p>Index 307</p>
Rubrieken
- advisering
- algemeen management
- coaching en trainen
- communicatie en media
- economie
- financieel management
- inkoop en logistiek
- internet en social media
- it-management / ict
- juridisch
- leiderschap
- marketing
- mens en maatschappij
- non-profit
- ondernemen
- organisatiekunde
- personal finance
- personeelsmanagement
- persoonlijke effectiviteit
- projectmanagement
- psychologie
- reclame en verkoop
- strategisch management
- verandermanagement
- werk en loopbaan