Changes between Version 106 and Version 107 of ProjectManagementIdeas


Ignore:
Timestamp:
Aug 1, 2011, 3:21:45 PM (13 years ago)
Author:
Chris Nelson
Comment:

Moved Related Research, again

Legend:

Unmodified
Added
Removed
Modified
  • ProjectManagementIdeas

    v106 v107  
    22
    33Trac is strong in basic, individual and small-team task management but lacks features for heavy-duty project management ''a la'' Microsoft Project, Project Manager Workbench, etc.  This page discusses those missing features and how they can best be realized.
     4
     5= Related research =
     6
     7Scheduling 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
     9There 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
     17A 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
     25All 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
     29Kolisch 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]
     34Kabeh Vaziri, Linda K. Nozick, Mark A. Turnquist
     35December 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]
     40Ningxiong Xu, Linda Nozick, Orr Bernstein, Dean Jones
     41December 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]
     48Robert C. Ash
     49December 1999           
     50
     51And others at [http://portal.acm.org/results.cfm?coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 ACM.org].
    452
    553= Requirements and Definitions =
     
    368416However, this doesn't seem to be all the data Project records for a task.  If you add a column to the WBS in the Gantt chart, there are many more options.  The most interesting is Work which is the amount of work required to complete a task.  Only when a resource is assigned 100% are Work and Duration the same.  We'd like to be specify the ''work'' required for a task and let the system calculate its ''duration'' based on available resources.
    369417
    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 
    419418= Roadmap =
    420419