As you can see from the previous sections of this thesis, both meta-heuristics and constraint programming perform well in some cases, but are inefficient or fail in others. Meta-heuristics work well even for large problems, as long as they are unconstrained, but as the number of constraints increases it gets harder for them to find any sort of feasible solution, let alone a good one. Constraint programming on the other hand works well for highly constrained problems, even if they are very large. In these cases you can select the method that works well in that particular situation and rely purely on that method. However, problems occur with substantially large problems which are too highly constrained for meta-heuristics to work well, but still have too many solutions to be considered by constraint programming so an optimal solution can be found. The apparently obvious answer seems to be to combine these two methods and exploit the advantages each of them offers.
Meyer and Ernst have successfully combined Ant Colony Optimisation (ACO) with Constraint Programming (CP) to create a hybrid optimisation method. The coupling between the two methods was done in the simplest possible way. Initial constraints, such as release and due dates, are posted initially before a schedule generation is started. From that point, the next job to be performed is selected using ACO. After a job is selected to be scheduled, additional constraints are posted, for example that that job has been scheduled at that position, the start and finish time of that job, and so on. This is repeated until all jobs have been scheduled, or there are no feasible jobs left at some point during the construction. Essentially, the meta-heuristic is influencing the order in which values are assigned to variables, i.e. value ordering for each of the variables.
Because of the way Bayesian Optimisation Algorithm (BOA) was designed, it is potentially more suitable for a use in a hybrid method with CP. This is because more information can be extracted from the network than in the case of ACO. To make it clear, let us examine a couple of examples.
Fixed network BOA + CP
Any fixed-network version of BOA can be coupled together with CP in identical fashion to Meyer and Ernst's CP-ACO hybrid method. However, the BOA-CP combination would be expected to work better than CP-ACO. Assuming the network accurately represents the relationships between variables in the problem, in this case job positions, in most fixed-network versions of BOA the choice of the next job to be scheduled using this network is likely to be better than with ACO. This is simply because at each step a more informed decision is made, not just analysing the previous job as ACO does, but other job positions as well, depending on the network. In addition, with BOA schedules are constructed by traversing the network, starting with jobs that do not have any parents and following their arcs. This means that the scheduled construction can start from any job position, not just the first. Because of this, a BOA-CP hybrid method would not just have an effect on the order in which jobs are assigned to a position (value ordering), but also on the order in which job positions are selected to be assigned a job (variable ordering).
Learning Network BOA + CP
Rather than using a fixed-network version of BOA with CP , a version that searches for the best network could also be combined with CP. BOA and CP could be coupled together in the same way as the fixed-network versions of BOA. However, this would mean that the best network would still have to be determined by some metric, such as the BD (Bayesian Dirichlet) metric. The testing of this version of BOA showed that the results were similar to the results of the two-predecessor fixed network version of BOA, but with a huge computational overhead of generating all possible Bayesian Networks at each generation and using the BD metric to select the best one. Here we can also assume that the advantage of getting a slightly better heuristic choice by finding the best network is cancelled out buy the extra work required to find the best network, especially since the BD metric relies on the data set being complete. In addition, constraint propagation could also prune the domains sufficiently enough to make the extra work done by BOA pointless, although this cannot be said for certain until a working version is implemented.
However, there is another possible way to combine BOA and CP that would further exploit the information that comes from the constraint propagation. In the basic coupling between any version of BOA described above and CP, BOA is used as the heuristic for value ordering, and occasionally variable ordering (non-predecessor networks). Constraint programming is used just to eliminate infeasible solutions from the search space, i.e. cut down the domains of variables. No further information is extracted from the constraint solver. To create a more sophisticated coupling between BOA and CP, whenever a job position is assigned a job we could keep track of domain reductions for each of the remaining job positions. This could be done simply by incrementing the count every time the domain gets reduced by adding the number of job ID's that have been removed from the domain of each variable (job position). This information could be used to construct the network. The bigger the domain reduction the more likely it is that there is a dependency between the two variables. This way the information that can be easily obtained from the solver is used to find the best Bayesian network for the problem, eliminating the need for constructing a large number of Bayesian networks and evaluating them using the BD metric. This idea looks to be most promising, and is definitely an idea worth pursuing.