The basic operation of Algorithm 2 is described here.
A set of directed disjunctive arcs can be made analogous to the path from the hive to the food source of a foraging bee. A bee that chooses to follow the path of another bee after watching the Waggle Dance will then take the whole set of directed disjunctive arcs and perform an additional swap on one of the disjunctive arcs that satisfy certain constraints based on a Theorem by Yamada (Yamada, 2003):
Theorem 1 (feasibility for adjacent exchange) Let S be a consistent complete selection and P(S) be a critical path in S. Consider a pair of adjacent critical operations (u; v) on a same machine on P(S), i.e., there is an arc selected from u to v. Then a complete selection Suv obtained from S by reversing the direction of the arc between u and v is always acyclic (thus the corresponding schedule is always feasible).
This is also known as the N1 neighborhood described in (Chavez et al., 2004).
The following terms used in Theorem 1 (Yamada, 2003) should be noted:
1. A selection is a set of directed arcs selected from the set of disjunctive arcs D
2. A selection is complete if all the disjunctive arcs in D are selected
3. A complete selection is consistent if the resulting directed graph is acyclic
At the start of a run of Algorithm2, the Shortest Process Time (SPT) dispatching rule is used to generate an initial solution. During the course of scheduling the operations to the machines using SPT rule, the directions of the disjunctive arcs are also updated. Finally, the critical path is generated from the schedule, and both the set of disjunctive arcs and the critical path are added to the Elite Solution List to kick start the algorithm.
After the initial solution is generated and added to the Elite Solution List, each bee will select an Elite Solution from the list with equal probability. For instance, if there were 5 Elite Solutions in the list, then the probability of selecting each Elite Solution will be 0.2.
Once the Elite Solution is chosen, the bee will choose a pair of operations that satisfy the constraints specified in Theorem 1 and swap them. The updated set of disjunctive arcs is then used to generate a new schedule, which is in turn used to generate the critical path. Elite Solutions are added to the Elite Solution List in three situations:
1. The solution from any bee will be added to the List of Elite Solutions with probability a
2. The best solution from each forage will be added to the List of Elite Solutions with probability b
3. The solution from any bee will be added to the List of Elite Solutions if its makespan is better than the current global best makespan.
To increase diversification, if the global best makespan has not improved for the past c iterations, the Elite Solution List is reset and the algorithm starts from the initial solution again.
Algorithm2 performed at 16.22% from the optimum, which was substantially poorer than that of Algorithm1 at 10.99%.
Several areas that might have caused the poor performance were identified as follows:
1. Each foraging bee will always choose to follow a waggle dancing bee (Elite Solution).
2. The initial solution is generated only from the Shortest Process Time dispatching rule and may therefore offer insufficient diversification.