452 | | |
| 452 | |
| 453 | 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]) and has been established to be [http://en.wikipedia.org/wiki/NP-hard NP hard]. There are several variations on the problem. |
| 454 | |
| 455 | ''RCPSP'' :: Resource-Constrained Project Scheduling Problem |
| 456 | |
| 457 | ''RCMPSP'' :: Resource-Constrained Multi-Project Scheduling Problem |
| 458 | |
| 459 | ''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.) |
| 460 | |
| 461 | A range of techniques have been brought to bear on RCPSP. They can be broadly categorized as: |
| 462 | |
| 463 | * 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). |
| 464 | |
| 465 | * Heuristic approximations. Attempts to find a good solution in reasonable time for a realistic number of tasks (e.g., hundreds). |
| 466 | |
| 467 | * Metaheuristics. More abstract approaches such as genetic algorithms, simulated annealing, ant colony optimization, and particle swarm optimization. |
| 468 | |
| 469 | 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. |
| 470 | |
| 471 | ---- |
| 472 | |