SOLVING LARGE-SCALE COMBINATORIAL OPTIMIZATION PROBLEMS BASED ON A DIVIDE-AND-CONQUER STRATEGY

A Hopfield neural network for a barge scale problem optimisation poses difficulties due to the issues of stability and the determination of network parameters. In this paper we introduce the concept of a divide and conquer algorithm to solve large scale optimisation problems usin g the Hopfield neural network. This paper also introduces the Grossber g Regularity Detector (GRD) neural network as a partition tool. This n eural network based partition tool has the advantages of reducing the complexity of partition selection as well as removing the recursive di vision process during the divide and conquer operation. A large scale combinatorial optimisation problem (i.e. sequence-dependent set-up tim e minimisation problem with a large number of parts (N > 100)) is line arly partitioned into smaller sets of sub-problems based on their simi larity relations. With a large number of parts (N > 100), the problem could not effectively be verified with other methods, such as the heur istic or branch and bound methods. Hence, the effectiveness of the div ide and conquer strategy implemented by the GRD neural network in conj unction with a Hopfield neural network was benchmarked against the fir st-come first-serve method, and the Hopfield neural network based on a rbitrary separations. The results showed that the divide and conquer s trategy of the GRD neural network was far superior to the other method s.