ACO applied to group shop scheduling: A case study on intensification and diversification

We present a MAX-MIN Ant System for the Group Shop Scheduling problem and propose several extensions aiming for a more effective intensification and diversification of the search process. Group Shop Scheduling is a general Shop Scheduling problem covering Job Shop Scheduling and Open Shop Scheduling. In general, in Shop Scheduling problems good solutions are scattered all over the search space. It is widely recognized that for such kind of problems, effective intensification and diversification mechanisms are needed to achieve good results. Our main result shows that a basic MAX-MIN Ant System – and potentially any other Ant Colony Optimization algorithm – can be improved by keeping a number of elite solutions found during the search, and using them to guide the search process.SCOPUS: cp.k3rd International Workshop on Ant Algorithms, ANTS 2002; Brussels; Belgium; 12 September 2002 through 14 September 2002; Code 145299