## 3 Ant Colony Optimization (ACO) Algorithm  
ACO algorithm [11; 12; 13] was developed based on the foraging behavior of ants in their colonies where pheromone is the substance used to communicate amongst the individuals. The ant that finds a food source will come back to its nest and deposits an amount of pheromone along the path. The ants tend to follow the path that has more pheromone deposited. Pheromone also evaporates over time. In this way, by depositing pheromone and following pheromone trails, ants can find a good approximation to the shortest path of the food source from their nest. ACO algorithm addressed job-shop scheduling problem firstly appeared in the literature which was known as Ant System (AS) in 1990s by [PERSON], [PERSON], et al. [14; 15]. Since then, several ACO variations were proposed such as ASElite, ASRank, Ant Colony System (ACS), Max-Min Ant System (MMAS) and Best-Worst Ant System (BWAS) [16]. Each algorithm enhanced the base algorithm in different ways. ASElite only used the best solution to update the pheromone. ASRank has a ranking system of subsets of solutions so only these are used for pheromone update. MMAS has bounded value  
Figure 1: Illustration of Maintenance, Repair, and Overhaul (MRO) processes. of pheromone and BWAS updated the pheromone only using the best and the worst solutions. Both exploration and exploitation mechanisms are adopted in ACS in order to widen the decision of path chosen in construction stage [17]. In addition, ACS also used local pheromone updating calculated at the end of each ant's construction step to diversify the path built by subsequent ants. ACS has been applied to job-shop scheduling problem to minimize the makespan [18; 19; 20] or tardiness [21; 22; 23]. In this paper, ACS is implemented to address MRO scheduling problem and described below. Figure 2 is a disjunctive graph to define the mathematical model of the ACO algorithm. Each node in the graph represents one operation of the jobs to be scheduled. Two more nodes are added into the graph, representing the starting and ending points. In the algorithm, each ant starts to visit all the nodes one-by-one from the starting node and complete its journey at the ending node. The schedule of the operations to be executed is constructed based on the sequence of the nodes that the ant has visited. All the operations are re-indexed from (0, 1, 2,..., \(N\), \(N+1\)), where 0 and (\(N+1\)) are the starting and ending nodes, respectively. The value \(\tau_{r,s}\) is the pheromone on the path that connects nodes \(r\) and \(s\). The arrowhead lines indicate the precedence constraints between the operations within the same job. For example, the arrowhead line connecting nodes 1 and 2 indicates that the ant must visit node 1 before it can visit node 2. In other words, the operation \(O_{1,1}\) must be executed before the operation \(O_{1,2}\)  
Initially, the pheromone values of all the possible paths are equal to an initial value, \(\tau_{0}\). Each ant of the colony builds a tour by repetitively using a random greedy rule called the state transition rule as defined in Equation (1). According to this rule, an ant will decide which path to follow based on the pheromone deposited on each feasible path. \[\left\{ \begin{array}{rl}\operatorname{argmax}_{u\in I(r)}\left\{\left[\tau(r,\,u)\right]\cdot\left[\eta(r,u)^{\beta}\right]\right\}&\text{if }q\leq q_{0}\ (\text{exploitation})\\ s&\text{otherwise }(\text{biased exploitation})\end{array} \right. \tag{1}\]  
\((r,\,u)\) represents the path connecting nodes \(r\) and \(u\), and \(\tau(r,\,u)\) is the pheromone value on that path.