The results of ACS testing and BOA testing have shown that a meta-heuristic on its own works quite well for unconstrained problems, even if they are quite large, but cannot cope with optimisation problems which are highly constrained. Constraint Programming on its own performed quite efficiently on these highly constrained problems, but did not do well with problems that had no constraints and therefore too many possible solutions. The biggest issue were the middle-band problems which were quite highly constrained but still had a large number of solutions to be considered. Here ACS and BOA on their own struggled to find any sort of feasible solution because the constraints were too tight. CP on the other hand always managed to find a solution, but it never got close to an optimum solution (within a million labelling steps), as the feasible space was still very large and a large number of feasible solutions existed.
The analysis of results obtained from ACS and BOA testing in this thesis pose a number of questions, and therefore a number of tests that still have to be performed. For a start, the proposed BOA-CP method was never implemented, and it is hard to predict how this method would perform without actually doing the tests. The first step would be to create a simple combined BOA-CP version, as described in the previous chapter, both with fixed and learning network versions of BOA. If this shows promising results, the next step would be to create the more sophisticated hybrid method, also described in the previous chapter, where we keep track of domain reductions and use them as the tool for learning the network structure. Once this is done, a comparison with the results obtained by Meyer and Ernst's CP-ACS method would hopefully reveal which method performed better and therefore seems to be the better choice for future research.
Once it is decided which combination to go for, i.e. BOA-CP or CP-ACO, there are still a number of improvements that can be made to the method. Meyer and Ernst's CP-ACS implementation used single-step backtracking during the construction of each schedule. There is no reason why this could not be extended to several steps, or even full backtracking (although you could argue that this should be handled by the constraint solver). Another improvement that could be made to both methods (CP-ACO and BOA-CP) is adding objective bounds as constraints. This would further prune the search space as only solutions better than the current solution would be considered feasible. The efficiency of algorithms would also have to be investigated, as CP on its own could be more efficient than a BOA-CP or a CP-ACO hybrid algorithm. A better comparison of efficiency could be achieved by improving the tree searching and improving the constraint modelling.
It is clear that the results obtained in this project have posed a number of questions and therefore a number of possible directions of research. Combining heuristics is currently an active area of research, and a good hybrid method could have a huge impact both on the academic community and the industry. Therefore it seems reasonable to pursue this idea of combining constraint programming with a meta-heuristic, especially the suggested more sophisticated combination of CP and BOA.