ACO for Assembly Line Balancing

An assembly line is made of $m$ workstations arranged in series and in parallel. The production program consists of a set $V$ of $n$ tasks with precedence relations that need to be assigned to the workstations.

Each task $j$ requires processing time $t_j>0$ and space $a_j$.

Each station $k$ has a cycle time $c_k$, to carry out a subset of $V,S_k$ tasks assigned to it (workload) and space area $A_k$.

Typically, the cycle time is the same for all workstations, $c$, which determines the production rate $r=1/c$. The cycle time represents an upper limit of the total time required by the tasks assigned to the workstation.

$I_k=c-t(S_k)$ is the idle time of workstation $k$. Total idle time is sum of all idle times over all stations.

The main object is to assign tasks to workstations to assign one or more of the following:

1. Minimize the number of workstations given a fixed value for the cycle time $c$ and space $A$
2. Minimize the cycle time $c$ given a fixed number of workstations $m$ and $A$
3. Minimize total space required given $c$ and $m$.
4. Give $m,c$ and $A$ find a feasible solution (assignment)

We can have multi-objectives, like do 1 and 2 given $A$, or do $1$ and $3$ given $c$.

Example:

ACO Solution

In TSP, each ant determines which city to add next to the solution, In this problem, each ant determines which assignment (task/workstation) to add next to the solution.

Each different assignment gets a pheromone trail parameter. A pheromone trail is associated with each assignment, where ${\tau }_{jk}$ denotes the pheromone trail associated with task $j$ getting assigned to workstation $k$.

Let $T$ be the set of tasks that are not yet assigned to a work station, whose predecessors are all assigned to work stations.

Then, we:

• Select max no of iterations, itmax
• Select number of Ants, antmax
• While number of iterations < itmax:
  • While current ant number < antmax:
    • Initialize ant parameters (pheromone, update, …, etc)
    • While ($T$ is not empty):
      • Select task $j$ to be assigned to workstation $k$ using transition rule.
      • If none of the tasks can be fit in the current workstation due to time or space capacity, open a new workstation
      • Update problem data
    • End ($T$ is empty)
    • Update pheromone trail using update rules and evaporation rule
    • Evaluate solution
  • Retain best solution of all ants
  • Update pheromone trail based on best solution (if desired)
• Return best solution

We can use the standard transition rules.

• Simple ratio

$$P_{ij}=\{\begin{array}{ll}\frac{{\tau }_{jk}^{\alpha }}{{\sum }_{n\in T}{\tau }_{nk}^{\alpha }}& \text{ if }j\in T,\\ 0& \text{otherwise}\end{array}$$

• Heuristics:

$$P_{ij}=\{\begin{array}{ll}\frac{[{\tau }_{ij}{]}^{\alpha }[{\eta }_j{]}^{\beta }}{{\sum }_{l\in T}[{\tau }_{ij}{]}^{\alpha }[{\eta }_j{]}^{\beta }}& \text{ if }j\in T,\\ 0& \text{otherwise}\end{array}$$

Heuristics can be related to utilization

$${\eta }_j=(1/c)\left(\sum _{l\in k}{t}_l+t_j\right)$$

or if the space is checked:

$${\eta }_j=(1/c)\left(\sum _{l\in k}{t}_l+t_j\right)+(1/A)\left(\sum _{l\in k}{a}_l+a_j\right)$$

The pheromone update and evaporation rule can be simple:

$${\tau }_{jk}=(1-\rho ){\tau }_{jk}+\Delta {\tau }_{jk}$$

where $\Delta {\tau }_{jk}$ can be density, quantity, or online delayed using utilization as solution quality.

We can also use a pheromone update on the best solution:

$${\tau }_{jk}=(1-\rho ){\tau }_{jk}+\rho \Delta {\tau }_{jk}^{\text{best}}$$