Solving real-time scheduling problems with Hopfield-type neural networks
Miguel Pedro Silva, Carlos Cardeira, Zoubir Mammeri · 2002
Real-time applications are increasingly becoming more complex, leading to the necessary development of fast scheduling algorithms. Therefore, the use of algorithms with a parallel search of feasible schedules seems to be attractive. In turn, Hopfield-type neural networks are suitable to solve complex combinatorial problems, owing to their fast convergence, if analog hardware is implemented. However, these neural networks have associated concepts of sub-optimality and the possibility of unfeasible solutions, which are contrary to the notion of system predictability. The paper presents a systematic procedure to map the scheduling problem onto a neural network in such a way that network solutions are always feasible schedules. Network convergence time is studied with digital computer simulations, using a discrete time model. Global asymptotic consistency between the discrete time model and the continuous one is assured. The paper also presents an analysis of the complexity of the proposed method.