Reducing network and computation complexities in neural based real-time scheduling scheme

摘要

Multiprocessor real-time scheduling is an important issue in many applications. A neural network provides a highly effective method to obtain good solutions for real-time scheduling problems. However, multiprocessor real-time scheduling problems include multiple variables; processor, process and time, and the neural networks have to be presented in three dimensions with these variables. Hence, the corresponding neural networks have more neurons, and synaptic weights, and thus associated network and computational complexities increase. Meanwhile, a neural network using the competitive scheme can provide a highly effective method with less network complexity. Therefore, in this study, a simplified two-dimensional Hopfield-type neural network using competitive rule is introduced for solving three-dimensional multiprocessor real-time scheduling problems. Restated, a two-dimensional network is proposed to lower the neural network dimensions and decrease the number of neurons and hence reduce the network complexity; an M-out-of-N competitive scheme is suggested to greatly reduce the computational complexity. Simulation results reveal that the proposed scheme imposed on the derived energy function with respect to process time and deadline constraints is an appropriate approach to solving these class scheduling problems. Moreover, the computational complexity of the proposed scheme is greatly lowered to O(N × T2).