The current implementation of Algorithm2 runs very slowly on large problems. This could be due to the computation of the critical path after every swap. It was noted that there is a necessity to pass through the digraph of the JSSP at least once every time the critical path is calculated. Coupled with the exponential relationship between the solution space and problem size, the consequences can be catastrophic (Chavez et al., 2004).
Researchers are currently testing out methods which do not require the calculation of the critical path in the job shop scheduling problem. Instead each pair of operations are evaluated to determine if they are in the critical path. In this way, there is no need to pass through the digraph; it is only necessary to check the given pair of operations. This new procedure would thus be able to make use of the N1 neighborhood while avoiding the problem of the long calculation time (Chavez et al., 2004).
2. Neighborhood Structure
The definition of a suitable neighborhood structure is one of the most important aspects of local search techniques (Musliu et al., 2004). The current neighborhood structure considered in the Disjunctive Graph Bee Colony Algorithm involves a single swap of operations on the same machine in the critical path. An alternative structure proposed by Yin (2004) can be adopted. It can be summarized as follows:
For a feasible solution DH, P(0, #) is a critical path of it. Let L(w, u) denote the length of the longest path from w to u in DH. Let (w, h1, h2, ... , hk) be a critical block, and p(w) be in this P(0, #). For any hi (i = 1, 2, ... , k), if L(0, w) >= L(0, p(hi)), then a backward move on w and hi will yield a new feasible solution, and this new solution can be considered as one of the neighbors of DH. Also, let (h1, h2, ... , hi, u) be a critical block, so s(u) be in this P(0, #). For any hj (j = 1, 2, ... , l), if L(0, s(hj)) >= L(0, u), then a forward move on hj and u will yield a new feasible solution, and this new solution can be considered as one of the neighbors of DH too. For all the critical blocks of P(0, #), one can test them by the use of the inequalities as described above to generate all neighbors of DH.
It was suggested that the new structure was able to strike a balance between the search speed and search space.
3. Incorporating Features Of Neighborhood Search
The current implementation of Algorithm2 has combined the strategies of Swarm Intelligence and Neighborhood Search. However, features of Neighborhood Search have not been incorporated into the algorithm. For instance, cycling has been observed in the algorithm. This can be overcome with the introduction of a Tabu List as in the Tabu Search Algorithm. Intensification and Diversification techniques described in the Tabu Search Algorithm can also be incorporated to further improve the performance of the algorithm. Further research in this direction may prove to be fruitful.
4. Visualization Using Gantt Charts
Previous and current research have been performed mainly based on numerical results. With the advancement of technology in terms of processing powers and capabilities of computers, a possible complement towards conventional research methods is through visualization of the Gantt charts of schedules produced by the algorithms under study. Analyzing these Gantt charts may reveal relationships that might have eluded researchers when analysis is made purely on the basis of numerical data. Interactive Gantt charts can also be developed such that the researcher can produce swaps manually and observe the results of each swap on the schedule. It is hoped that with such a visualization tool, researchers can identify better techniques to perform local search, or define more effective neighborhood structures.
5. Incorporating More And Better Dispatching Rules
It was seen that having a larger number of dispatching rules usually led to better results. However, it was also suggested that significant improvements cannot be achieved by simply increasing the number of dispatching rules without considering the effectiveness of the rules introduced and the number of bees assigned to each dispatching rule. This was evident in the experiments discussed in the report..
Hence, more research in this area would be helpful. Several questions have yet to be answered:
1. How many bees are required for each dispatching rule to adequately exploit its advantage?
2. What is the maximum number of dispatching rules that can be used without increasing computational time beyond reasonable limits?
3. Can the algorithm be run in parallel on several computers to accommodate more dispatching rules?
It is hoped that further research in this area will result in more diverse and promising initial solutions that the algorithm can build upon to generate better makespans.