This page gives a brief overview of the results obtained by applying our two ACS implementations on a number of job scheduling problems, as well as a comparison of how the methods performed against each other and against Meyer and Ernst's ACS implementation. Tables 1 and 2 provide an overview of the results of ACS-H1 and ACS-H2 implementations for each of the sample problems. For both implementation, the table give the best solution found, the average solution over 10 runs, as well as the failure rate.
ACS with Shortest Setup Time Heuristic - ACS-H1
As was expected, this implementation performed, in most cases, slightly worse than Meyer and Ernst's implementation. For most of the small problems, such as W8.1 (8 jobs) and RBG10.a (10 jobs - see Appendix C), both versions find the optimal solution every time. However, the difference in the two methods becomes apparent as the problem size and constraint tightness increase. In some of the larger problems, for example W20.3 and W30.3, Meyer and Ernst's implementation finds a better solution and has a better average. In addition, in some cases our ACS version does not find any feasible solutions (e.g. W20.1, W30.1, BR17.a.17), whereas the Meyer and Ernst version finds a feasible solution either always (W20.1) or sometimes (W30.1, BR17.a.17). However, there were cases where ACS-H1 performed better. With problem RBG21.9, ACS-H1 has a slightly better average, as well as the best solution found. Another problem where it performs better is problem RBG27.a.3, where both the best solution and the average are exceedingly better than the ones obtained by Meyer and Ernst's implementation. These exceptions could be explained by the fact that Meyer and Ernst's version is creating less schedules, stopping after a million labelling steps, while ACS-H1 and ACS-H2 are creating a million schedules. However, these exceptions could be due to something that is specific to these problems and in general Meyer and Ernst's version is superior, as expected.
ACS with Next Job Due Heuristic - ACS-H2
As mentioned earlier in this section, this version uses a heuristic that aims primarily at obtaining a feasible solution, by assigning jobs heuristic values proportionally to their due date, meaning that the earlier the job is due the higher its heuristic value will be. Again, for the small problems (W8.1, RBG10.a), this implementation performed equally to ACS-H1 and Meyer and Ernst's implementation. Again, as the problem size and the degree of tightness increase, the difference between ACS-H2 and the other two implementations becomes apparent. The results obtained by ACS-H2 are slightly worse than those obtained by ACS-H1, and therefore slightly worse than the results obtained by Meyer and Ernst. However, there are cases where this version proved to be more reliable in finding a feasible solution where ACS-H1 failed to find any sort of feasible solution (W20.1, W30.1, RBG16.a and BR17.a.10 ). Also, with problem RBG16.b, ACS-H2 proved to be not just more reliable, but also had a better average and best solution. In addition, there were a couple of problems where ACS-H2 performed better than Meyer and Ernst's version. In problem W30.1, where Meyer and Ernst's implementation had a 60% failure rate, this implementation never failed. It seems dubious that this occurs, as the same heuristic (next job due) is used initially in Meyer and Ernst's implementation. The answer could again be that the million labelling steps performed by that implementation (compared to a million by ACS-H1 and ACS-H2) are not enough to create the required number of schedules to get to a feasible schedule. However, the quality of the solutions found was not as good as the solutions found by Meyer and Ernst. Another exception was problem RBG27.a.3, where the best and average solution obtained by ACS-H2 were considerably better than solutions found by Meyer and Ernst, but by almost the same margin worse than the results for the same problem obtained by ACS-H1.