Changes between Version 105 and Version 106 of ProjectManagementIdeas


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

Moved Related Research

Legend:

Unmodified
Added
Removed
Modified
  • ProjectManagementIdeas

    v105 v106  
    368368However, 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.
    369369
     370= Related research =
     371
     372Scheduling 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
     374There 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
     382A 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
     390All 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
     394Kolisch 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]
     399Kabeh Vaziri, Linda K. Nozick, Mark A. Turnquist
     400December 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]
     405Ningxiong Xu, Linda Nozick, Orr Bernstein, Dean Jones
     406December 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]
     413Robert C. Ash
     414December 1999           
     415
     416And others at [http://portal.acm.org/results.cfm?coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 ACM.org].
     417
     418
    370419= Roadmap =
    371420
     
    479528   * "fit" - It's better to start a 2-day task on Wednesday and hold a 4 day task for the next week than to break up the longer task across a weekend.
    480529
    481 === Related research ===
    482 
    483 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]. 
    484 
    485 There are several variations on the problem.
    486 
    487  ''RCPSP'' :: Resource-Constrained Project Scheduling Problem
    488 
    489  ''RCMPSP'' :: Resource-Constrained Multi-Project Scheduling Problem
    490 
    491  ''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.)
    492 
    493 A range of techniques have been brought to bear on RCPSP.  They can be broadly categorized as:
    494 
    495  * 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).
    496 
    497  * Heuristic approximations. Attempts to find a good solution in reasonable time for a realistic number of tasks (e.g., hundreds).
    498 
    499  * Metaheuristics.  More abstract approaches such as genetic algorithms, tabu search, simulated annealing, ant colony optimization, and particle swarm optimization.
    500 
    501 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.
    502 
    503 [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.
    504 
    505 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. 
    506 
    507 ----
    508 
    509 [http://portal.acm.org/citation.cfm?id=1162708.1163079&coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 Resource allocation and planning for program management]
    510 Kabeh Vaziri, Linda K. Nozick, Mark A. Turnquist
    511 December 2005           
    512 
    513   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 ...
    514 
    515 [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]
    516 Ningxiong Xu, Linda Nozick, Orr Bernstein, Dean Jones
    517 December 2007           
    518 
    519  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 ...
    520 
    521 
    522        
    523 [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]
    524 Robert C. Ash
    525 December 1999           
    526 
    527 And others at [http://portal.acm.org/results.cfm?coll=ACM&dl=ACM&CFID=42032534&CFTOKEN=18432343 ACM.org].
    528 
    529530== Other `tracpm` functions ==
    530531