| 4 | |
| 5 | = Related research = |
| 6 | |
| 7 | Scheduling activities in a project is an area of active research in operational research (or operations research, [http://en.wikipedia.org/wiki/Operations_research OR]) (cf. [http://books.google.com/books?id=pHetPl2LOYgC&lpg=PA153&ots=rKKZ7Lv2On&dq=pslib%20project%20scheduling&pg=PP1 Project Scheduling]) and has been established to be [http://en.wikipedia.org/wiki/NP-hard NP hard]. |
| 8 | |
| 9 | There are several variations on the problem. |
| 10 | |
| 11 | ''RCPSP'' :: Resource-Constrained Project Scheduling Problem |
| 12 | |
| 13 | ''RCMPSP'' :: Resource-Constrained Multi-Project Scheduling Problem |
| 14 | |
| 15 | ''m_PRCPSP'' :: Preemptable RCPSP. A RCPSP where each task may be broken (preempted) ''m'' times during scheduling. (Generally, ''m'' is limited to 1 both for simplicity of the algorithm and because there is real cost in practical task switching.) |
| 16 | |
| 17 | A range of techniques have been brought to bear on RCPSP. They can be broadly categorized as: |
| 18 | |
| 19 | * Exact solutions. Attempts to find an optimal schedule. Due to the polynomial nature of the problem these are only possible or practical for a small number of activities (e.g., a few dozen). |
| 20 | |
| 21 | * Heuristic approximations. Attempts to find a good solution in reasonable time for a realistic number of tasks (e.g., hundreds). |
| 22 | |
| 23 | * Metaheuristics. More abstract approaches such as genetic algorithms, tabu search, simulated annealing, ant colony optimization, and particle swarm optimization. |
| 24 | |
| 25 | All of these algorithmic approaches also have other dimensions such as the number of threads that are used, the method they use to prioritize activities, etc. To be practical for implementation as a Trac plugin, it seems likely our implementation should not require heavy-weight, opaque abstractions or multiple threads. Furthermore, we desire an algorithm which can ''update'' a schedule as part of a ticket change listener rather than having to completely recompute a schedule for each, individual change. |
| 26 | |
| 27 | [http://129.187.106.231/psplib/ PSPLIB] provides a standard set of program scheduling problems to test the various algorithms performance against one another and the optimal solution. |
| 28 | |
| 29 | Kolisch and Hartmann[[FootNote(Kolisch, R. & Hartmann S. "Experimental investigation of heuristics for resource-constrained project scheduling: An update" European Journal of Operational Research 174 (2006): 23-27.)]] tested dozens of algorithms and variations using the PSPLIB data. |
| 30 | |
| 31 | ---- |
| 32 | |
| 33 | [http://portal.acm.org/citation.cfm?id=1162708.1163079&coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 Resource allocation and planning for program management] |
| 34 | Kabeh Vaziri, Linda K. Nozick, Mark A. Turnquist |
| 35 | December 2005 |
| 36 | |
| 37 | Much of the project scheduling literature treats task durations as deterministic. In reality, however, task durations are subject to considerable uncertainty and that uncertainty can be influenced by the resources assigned. The purpose of this paper ... |
| 38 | |
| 39 | [http://portal.acm.org/citation.cfm?id=1351542.1351869&coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 Stochastic rollout and justification to solve the resource-constrained project scheduling problem] |
| 40 | Ningxiong Xu, Linda Nozick, Orr Bernstein, Dean Jones |
| 41 | December 2007 |
| 42 | |
| 43 | 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 ... |
| 44 | |
| 45 | |
| 46 | |
| 47 | [http://portal.acm.org/citation.cfm?id=324898.324933&coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 Activity scheduling in the dynamic multi-project setting: choosing heuristics through deterministic simulation] |
| 48 | Robert C. Ash |
| 49 | December 1999 |
| 50 | |
| 51 | And others at [http://portal.acm.org/results.cfm?coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 ACM.org]. |
370 | | = Related research = |
371 | | |
372 | | Scheduling activities in a project is an area of active research in operational research (or operations research, [http://en.wikipedia.org/wiki/Operations_research OR]) (cf. [http://books.google.com/books?id=pHetPl2LOYgC&lpg=PA153&ots=rKKZ7Lv2On&dq=pslib%20project%20scheduling&pg=PP1 Project Scheduling]) and has been established to be [http://en.wikipedia.org/wiki/NP-hard NP hard]. |
373 | | |
374 | | There are several variations on the problem. |
375 | | |
376 | | ''RCPSP'' :: Resource-Constrained Project Scheduling Problem |
377 | | |
378 | | ''RCMPSP'' :: Resource-Constrained Multi-Project Scheduling Problem |
379 | | |
380 | | ''m_PRCPSP'' :: Preemptable RCPSP. A RCPSP where each task may be broken (preempted) ''m'' times during scheduling. (Generally, ''m'' is limited to 1 both for simplicity of the algorithm and because there is real cost in practical task switching.) |
381 | | |
382 | | A range of techniques have been brought to bear on RCPSP. They can be broadly categorized as: |
383 | | |
384 | | * Exact solutions. Attempts to find an optimal schedule. Due to the polynomial nature of the problem these are only possible or practical for a small number of activities (e.g., a few dozen). |
385 | | |
386 | | * Heuristic approximations. Attempts to find a good solution in reasonable time for a realistic number of tasks (e.g., hundreds). |
387 | | |
388 | | * Metaheuristics. More abstract approaches such as genetic algorithms, tabu search, simulated annealing, ant colony optimization, and particle swarm optimization. |
389 | | |
390 | | All of these algorithmic approaches also have other dimensions such as the number of threads that are used, the method they use to prioritize activities, etc. To be practical for implementation as a Trac plugin, it seems likely our implementation should not require heavy-weight, opaque abstractions or multiple threads. Furthermore, we desire an algorithm which can ''update'' a schedule as part of a ticket change listener rather than having to completely recompute a schedule for each, individual change. |
391 | | |
392 | | [http://129.187.106.231/psplib/ PSPLIB] provides a standard set of program scheduling problems to test the various algorithms performance against one another and the optimal solution. |
393 | | |
394 | | Kolisch and Hartmann[[FootNote(Kolisch, R. & Hartmann S. "Experimental investigation of heuristics for resource-constrained project scheduling: An update" European Journal of Operational Research 174 (2006): 23-27.)]] tested dozens of algorithms and variations using the PSPLIB data. |
395 | | |
396 | | ---- |
397 | | |
398 | | [http://portal.acm.org/citation.cfm?id=1162708.1163079&coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 Resource allocation and planning for program management] |
399 | | Kabeh Vaziri, Linda K. Nozick, Mark A. Turnquist |
400 | | December 2005 |
401 | | |
402 | | Much of the project scheduling literature treats task durations as deterministic. In reality, however, task durations are subject to considerable uncertainty and that uncertainty can be influenced by the resources assigned. The purpose of this paper ... |
403 | | |
404 | | [http://portal.acm.org/citation.cfm?id=1351542.1351869&coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 Stochastic rollout and justification to solve the resource-constrained project scheduling problem] |
405 | | Ningxiong Xu, Linda Nozick, Orr Bernstein, Dean Jones |
406 | | December 2007 |
407 | | |
408 | | 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 ... |
409 | | |
410 | | |
411 | | |
412 | | [http://portal.acm.org/citation.cfm?id=324898.324933&coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 Activity scheduling in the dynamic multi-project setting: choosing heuristics through deterministic simulation] |
413 | | Robert C. Ash |
414 | | December 1999 |
415 | | |
416 | | And others at [http://portal.acm.org/results.cfm?coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 ACM.org]. |
417 | | |
418 | | |