2
$\begingroup$

Suppose there are $n$ tasks assigned to $n$ workers, and each worker can be assigned only one task. Each worker can complete any one of the tasks, but the time spent varies. Use the ant colony algorithm to find the best allocation scheme that minimizes the total time spent. And firstly, how to build a mathematical model to describe the problem?

$\endgroup$
2
  • 3
    $\begingroup$ Welcome to OR.SE. Based on what you mentioned, this is a simple assignment problem. If you have a resource limitation, the problem can be interpreted as a generalized assignment problem. As a template, this might be useful. $\endgroup$
    – A.Omidi
    Commented Mar 7, 2022 at 10:20
  • $\begingroup$ Also, the assignment problem is easy to solve to proven optimality (either as a linear program or using the "Hungarian algorithm"), so it is an unlikely candidate for ACO (unless this is a rather funky homework question). I think the formulation for ACO would look rather different than the common formulation. $\endgroup$
    – prubin
    Commented Mar 7, 2022 at 22:23

1 Answer 1

2
$\begingroup$

If you really have to do it, perhaps for understanding the mechanics of ACO, here is a possibility.

First, lets write a mathematical model for the problem. Let $x_{ij}$ be a binary variable that takes value $1$ if and only if worker $i$ is assigned to task $j$. Let $c_{ij}$ denote the time it takes for worker $i$ to complete task $j$. You want to minimize total time: $$ \min \; \sum_{i,j} c_{ij} x_{ij} $$ subject to:

  • one task per worker: $$ \sum_{j} x_{ij}=1 \quad \forall i $$
  • one worker per task: $$ \sum_{i} x_{ij}=1 \quad \forall j $$

It is useful to have this model because the underlying structure is a bipartite graph $G=(V,A)$, where $V=U_1 \cup U_2$ is the node set with $U_1$ for the workers and $U_2$ for the tasks.

With such a structure, you could, for example (and there are many other ways to do this), put ants on each of the vertices $u\in U_1$, and define an ant move along an edge $(u,v)$ towards a node $v\in U_2$. An ant on node $u$ always moves along the first node $v$ that is available, such that $c_{uv}$ is minimal. This defines a feasible solution.

The way an ant $i$ is chosen to make this move depends on two factors:

  1. the attractiveness of node $i$, denoted by $A(i)$. This could be, for example, $A(i)=C-\min_{j\in \hat{U}_2}c_{ij}$, where $C$ is the highest $c_{uv}$, and $\hat{U}_2$ the set of available tasks. So a node is attractive if it is linked to another unassigned node $j$ with a small $c_{ij}$.
  2. the trail level of the node $i$, denoted by $T(i)=t(i,j)$, which is an indication of how proficient it has been in the past to assign node $i$ to node $j$.

The next ant $i$ that is selected to make its move is made according to the ACO probability: $$ p(i) = \frac{A(i)^{\alpha}T(i)^{\beta}}{\sum_{v\in W }A(v)T(v)} $$ where $\alpha$ and $\beta$ are two parameters which give more or less importance to the attractiveness and trail level, and $W \subseteq U_1$ is the set nodes that have not been processed yet.

Initially, terms $t(i,j)$ all have value $0$. At each iteration, the objective function is computed, let $z$ be its value. Terms $t_{ij}$ are increased by a $1/z$, and regularly decrease with the help of $\rho$, the pheromone evaporation coefficient.

In essence, with this scheme, you have a randomized greedy algorithm. Greedy because given a worker $i$, you assign it to task $j$ with lowest $c_{ij}$ such that $j$ is available. Randomized because the order in which workers are processed is randomized according to the classical mechanics of ACO. There are many other options. And again, this is purely for understanding purposes, as efficient optimal algorithms exist, as mentioned in the comments.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.