DocumentCode :
2618242
Title :
Stochastic rollout and justification to solve the resource-constrained project scheduling problem
Author :
Xu, Ningxiong ; Nozick, Linda ; Bernstein, Orr ; Jones, Dean
Author_Institution :
Cornell Univ., Ithaca
fYear :
2007
fDate :
9-12 Dec. 2007
Firstpage :
1820
Lastpage :
1827
Abstract :
The key question addressed by the resource-constrained project scheduling problem (RCPSP) is to determine the start times for each activity such that precedence and resource constraints are satisfied while achieving some objective. Priority rule-based heuristics are widely used for large problems and more recently justification has been shown to be an important extension. Xu et al. further augments priority rule heuristics by creating rollout procedures and proves their effectiveness. However, that procedure generates just one schedule. We extend that method using sampling to generate a set of schedules using probabilistic techniques and select the best schedule from this sample. Using the 600 problem instances in PSLIB, we present empirical evidence that this procedure produces solutions that are better than the rollout procedure alone but at a computational cost.
Keywords :
constraint theory; probability; project management; resource allocation; sampling methods; scheduling; stochastic processes; priority rule-based heuristics; probabilistic techniques; resource-constrained project scheduling problem; sampling method; stochastic justification; stochastic rollout; Computational efficiency; Investments; Laboratories; Linear programming; Machining; Processor scheduling; Production planning; Sampling methods; Simulated annealing; Stochastic processes;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Simulation Conference, 2007 Winter
Conference_Location :
Washington, DC
Print_ISBN :
978-1-4244-1306-5
Electronic_ISBN :
978-1-4244-1306-5
Type :
conf
DOI :
10.1109/WSC.2007.4419808
Filename :
4419808
Link To Document :
بازگشت