Multiconstraint task scheduling in multi-processor system by neural network
Ruey‐Maw Chen, Yueh‐Min Huang · 2002
The traveling salesman problem (TSP), a typical combinatorial explosion problem, has been well studied in the AI area, and neural network applications to solve the problem are widely surveyed as well. The Hopfield neural network is commonly referred to in finding an optimal solution and a fast convergence to the result, however, it often traps to a local minimum. Stochastic simulated annealing has an advantage in finding the optimal solution; it provides a chance to escape from the local minimum. Both significant characteristics of the Hopfield neural network structure and stochastic simulated annealing algorithm are combined together to yield a so called mean field annealing technique. A complicated job scheduling problem of a multiprocessor with multiprocess instance under execution time limitation process migration inhibited and bounded available resource constraints is presented. An energy based equation is developed first whose structure depends on precise constraints and acceptable solutions using an extended 3D Hopfield neural network (HNN) and the normalized mean field annealing (MFA) technique; a variant of mean field annealing was conducted as well. A modified cooling procedure to accelerate a reaching equilibrium for normalized mean field annealing was applied to the study. The simulation results show that the derived energy function worked effectively, and good and valid solutions for sophisticated scheduling instance can be obtained using both schemes.