It was suggested by some researchers that insects such as ants and honey bees possess characteristics known collectively as Swarm Intelligence that makes models of their behavior suitable for solving distributed optimization problems. Indeed, the Ant Colony Algorithm has been well-researched and proven to perform reasonably well. However, little research has been done on simulating the Bee Colony to solve job shop scheduling problems. This project was thus carried out to study the effects of modeling the Bee Colony into an algorithm to solve job shop scheduling problems.
The main focus of this project is to study the features of the natural honey bee colony, and incorporate their effective foraging capabilities into an algorithmic structure that can be used to solve job shop scheduling problems. Initial analysis was performed on the Bee Colony system proposed by Chong, Low, Sivakumar, & Gay (2006). The algorithm performed at 10.99% from the optimum based on a set of 82 well-known benchmark problems. Several modifications were made to the algorithm and minor improvements were observed. The best result obtained was 10.76% from the optimum, which was an improvement of 0.23%.
A novel Bee Colony algorithm was also introduced to solve the Job Shop Scheduling Problem based on a disjunctive graph representation. This approach seeks to exploit the capabilities of Swarm Intelligence and the benefits of Neighbourhood Search. Numerous variations of this algorithm was introduced and evaluated. The best result obtained was 12.80% from the optimum based on a set of 82 well-known benchmark problems, which was close to that of the Ant Colony Algorithm at 11.45% from the optimum. This novel approach appears to be promising and several possible directions for future research were also discussed towards the end of this report.
It is hoped that findings from this project would be able to contribute towards advancement in this difficult problem, where the optimum solution has eluded researchers worldwide for so long.