Ant colony algorithm based scheduling for handling software project delay

Wei Zhang, Yun Yang, Junchao Xiao, Xiao Liu, Muhammad Ali BabarICSSP 2015 · DOI

TL;DR

This paper tackles the critical issue of software project delays by proposing a novel Ant Colony Optimization (ACO) algorithm. The algorithm intelligently reallocates skilled employees between concurrent projects to mitigate delays without causing new ones, a complex NP-hard problem.

What Problem Does This Paper Address?

Software projects often face delays, which can severely impact customer satisfaction, company reputation, and profitability. While adding resources is a common solution, it can lead to "delay propagation" due to learning curves and communication overhead. This paper focuses on a more nuanced problem: how to effectively reallocate existing skilled employees between multiple concurrent projects to eliminate or minimize delays on critical paths. The challenge lies in the fact that reallocating an employee from one project to help another might inadvertently cause delays in the donor project, creating a complex combinatorial optimization problem.

Methods

The core of this paper is the proposal of an Ant Colony Optimization (ACO) algorithm to address the complex scheduling problem. Traditional approaches like Critical Path Method (CPM) and Program Evaluation and Review Technique (PERT) are mentioned, but they don't adequately handle runtime delays and inter-project resource reallocation. The authors frame the problem as finding an optimal combination of employee assignments and activity scheduling across multiple projects.

The ACO algorithm works by simulating ants that traverse a "search tree" representing possible scheduling combinations. Each ant explores different ways to assign employees to activities, considering whether an activity can be partitioned and if a help employee from another project can be brought in. The algorithm iteratively refines these assignments based on simulated pheromone trails, guiding subsequent ants towards more promising solutions. A key component is the SelectNode function, which dictates how ants choose the next combination to explore, considering factors like employee availability and potential duration reductions.

Datasets

Not discussed in the paper. The authors use hypothetical case studies with randomly generated parameters for evaluation.

Key Insights and Ideas

  • Delay Propagation is a Complex Interdependency: The paper highlights that simply assigning more resources to a delayed activity can have ripple effects, potentially delaying other activities or even other projects. This underscores the need for a holistic scheduling approach.
  • Reallocation is Not Always Straightforward: The authors demonstrate that not all delayed activities benefit from immediate intervention. Sometimes, it's more effective to allow a delay to propagate to a subsequent activity where a more efficient reallocation can occur.
  • Order Matters: The sequence in which employees are reallocated and activities are scheduled significantly impacts the final outcome. This is a crucial aspect that the ACO algorithm aims to optimize.
  • NP-Hardness of the Problem: The paper clearly articulates that finding the optimal solution for employee scheduling across multiple projects is an NP-hard problem, justifying the need for heuristic algorithms like ACO.

Key Results

The paper presents two case studies and simulation experiments to validate their ACO algorithm.

  • Case Study 1 (Two Projects): The algorithm successfully eliminated an 8-day delay in one project (cp1) without introducing any delay into the second project (cp2).
  • Case Study 2 (Three Projects): The algorithm reduced a 10-day delay in one project (cp1) to a 2-day delay, while keeping the other two projects (cp2 and cp3) on schedule.
  • Simulation Experiments: The simulations showed a high and stable "hit count" (number of feasible solutions found) across varying numbers of paths (projects) and activities, indicating the algorithm's robustness in finding feasible solutions quickly. The computation time for these simulations was less than a minute.

Limitations and Future Work

The authors acknowledge that their current work is based on several simplifying constraints:

  • An activity is helped by at most one extra employee.
  • Activities cannot be interrupted once started.
  • The problem is simplified to scenarios with a limited number of concurrent projects.

Future work will focus on relaxing these constraints to make the algorithm more general and applicable to more realistic scenarios. This includes exploring scenarios with multiple help employees per activity, interruptible activities, and a larger number of concurrent projects.

Summary updated

BibTeX
@inproceedings{zhang2015ant,
  author = {Wei Zhang and Yun Yang and Junchao Xiao and Xiao Liu and Muhammad Ali Babar},
  title = {{Ant colony algorithm based scheduling for handling software project delay}},
  booktitle = {ICSSP},
  year = {2015},
  doi = {10.1145/2785592.2785603},
}
Figure