A total of 3 modifications were made to Algorithm1. They are as follows:
1. Modified Elite Solution (Algorithm1_Mod1)
The original implementation assigns a probability to decide whether to add a solution to the Elite Solution List irregardless of its makespan. Therefore, there is a possibility that a bad solution is added to the list, and subsequently be followed by other bees.
The modified version maintains a list of only the current best solutions in the Elite Solution List. It achieves an average improvement of 0.23% closer to the optimum.
2. Modified Deviation (Algorithm1_Mod2)
The original implementation uses a probability to decide, at the scheduling point of each operation, whether to follow the operation link in the Elite Solution chosen, or not to follow that operation link. It was thought that this model of deviation from the Elite Solution did not coincide with that of a natural bee.
The modified version uses a pseudo-random generator to generate a factor between 0 and 0.8. This factor will then be used to determine the number of nodes that the bee will follow the Elite Solution. For instance, if the factor is 0.2, the bee will follow through the first 20% of the nodes in the Elite Solution. This version achieved an average improvement of 0.17% closer to the optimum.
3. Division into Separate Groups (Algorithm1_Mod3)
The original implementation uses only one group of 20 bees. It was thought that dividing the 20 bees into more groups might help the algorithm to achieve diversification.
Hence, in the modified version, the 20 bees are divided into 4 groups of 5 bees instead. Each group operated independently of the others, and has its own Elite Solution List. This version achieved an average improvement of only 0.04% closer to the optimum. A possible reason is that although having more independent groups offered greater diversification, having only 5 bees per group also resulted in insufficient intensification.
It was observed that limited improvements were achieved by the modifications discussed above. This could be due to insufficient diversification.
At this point, it is essential to discuss brieftly the issue of machine-centric and operation-centric immplementations of Algorithm1. More detailed discussions are found in the report.
The machine-centric implementation schedules operations from the point of view of the machines, and generates Non-delay schedules. The operation-centric implementation schedules operations from the point of view of the operations, and generates both Active and Non-delay schedules. The figure below shows the relationships between the various types of schedules.
