Changes between Version 105 and Version 106 of ProjectManagementIdeas


Ignore:
Timestamp:
Aug 1, 2011 5:17:32 PM (3 years ago)
Author:
ChrisNelson
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