 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Algorithm1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| This page describes the main components of the Bee Colony algorithm proposed by Chong et al. (2006). This algorithm will be referred to as Algorithm1. 3 key areas of Algorithm will be discussed: 1. Waggle Dance 2. Forage 3. Algorithmic Framework 1. In order to model the Waggle Dance, the profitabilities of a forager and the colony are defined as follows: |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Related Links: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Main Page | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Background of the JSSP | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Why the Bee Colony was Chosen? | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Modeling the JSSP as a Bee Colony | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Algorithm1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Modifications of Algorithm1 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Algorithm2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Modifications of Algorithm2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Profiling | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| where |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Proposed Future Directions | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Conclusion | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| n | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| : number of bees performing waggle dance | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| References | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| : makespan of bee i | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| My Info: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| : makespan of bee j | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Name: | Yeo Lian Sheng | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Email: | [email protected] | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| The lookup table shown below is then used to determine the probability (r) that a bee will follow the path of the waggle dancers. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| In the implementation of the algorithm, a data structure known as the Elite Solution is used to represent a waggle dancing bee. All Elite Solutions are stored in the Elite Solution List. Pfcolony is thus the average makespan of all the Elite Solutions in the Elite Solution List. 2. In order to model the forage process, a function to decide which operations to schedule is required. Such a function is defined as follows: |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| : rating of the edge between nodes i and j | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
: processing time of node j | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| : probability of transition from i to j | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| : constant for the preferred path | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| k | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| : number of nodes | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| : presence of preferred path (0: no preferred path; 1: preferred path exists) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| m | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 3. The algorithmic framework shown below is used to solve the JSSP: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| For every iteration, each bee will perform a forage. If the schedule it produces has a makespan which is better than that of the current best, the current best makespan will be updated and the bee will perform a waggle dance (adds schedule to Elite Solution List). With a small probability, a randomly chosen bee may perform a waggle dance irregardless of its makespan. After the last iteration has been completed, the best solution will be presented as the final solution of the algorithm. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||