Composing Approximated Algorithms Based on Hopfield Neural Network for Building a Resource-Bounded Scheduler

Abstract 2. Scheduling problem In previous work we have studied the Hopjield Artificial Neural Network model and its use for solving a particular scheduling problem: non pre-emptive tasks with release times, deadlines and computation times to be scheduled on several uniform machines. We presented an iterative approach based on Hopfield Networks which enables resource-bounded reasoning. We have validated our approach on a great number of randomly generated examples. Results are better than an efjicient scheduling heuristics when no timing constraint exists and our system is able to adapt its behavior when timing constraints are imposed by the application. In this papeG we extend this work by studying the incidence of two kinds of approximations on the processing time and on the success rate, so as to decide what sequence of activations for the contract will be likely to give the best success rate. 1. Hopfield Neural Network The Hopfield Model [2] is made up of a set of fully interconnected processing elements. The model relies on three major forms of parallel organization: parallel input channels, parallel output channels and parallel computation of the processing entities (called neurons). Each neuron has an external input, performs a weighted sum of all its inputs and applies a sigmoid function to the result to obtain a value in the interval [O,l]. The initial state of the network depends on the input. When new values of the neurons are computed, this temporary state evolves to reach a stable state, where all neurons remain constant (set to 0 or 1). This evolution corresponds to the minimization of the global energy of the net. It can be modeled by an energy function depending on the weights of the connections and the input values. Therefore, when an initial set of inputs is provided, the system converges to a stable state that minimizes the function