A Neurodynamic Approach for Real-Time Scheduling via Maximizing Piecewise Linear Utility
In this paper, we study a set of real-time scheduling problems whose objectives can be expressed as piecewise linear utility functions. This model has very wide applications in scheduling-related problems, such as mixed criticality, response time minimization, and tardiness analysis. Approximation schemes and matrix vectorization techniques are applied to transform scheduling problems into linear constraint optimization with a piecewise linear and concave objective; thus, a neural network-based optimization method can be adopted to solve such scheduling problems efficiently. This neural network model has a parallel structure, and can also be implemented on circuits, on which the converging time can be significantly limited to meet real-Time requirements. Examples are provided to illustrate how to solve the optimization problem and to form a schedule. An approximation ratio bound of 0.5 is further provided. Experimental studies on a large number of randomly generated sets suggest that our algorithm is optimal when the set is nonoverloaded, and outperforms existing typical scheduling strategies when there is overload. Moreover, the number of steps for finding an approximate solution remains at the same level when the size of the problem (number of jobs within a set) increases.
Z. Guo and S. K. Baruah, "A Neurodynamic Approach for Real-Time Scheduling via Maximizing Piecewise Linear Utility," IEEE Transactions on Neural Networks and Learning Systems, vol. 27, no. 2, pp. 238 - 248, Institute of Electrical and Electronics Engineers (IEEE), Feb 2016.
The definitive version is available at https://doi.org/10.1109/TNNLS.2015.2466612
Intelligent Systems Center
Keywords and Phrases
Neurodynamic optimization; NP-hard problem; overloaded job set; real-Time scheduling; recurrent neural network (RNN); utility maximization
International Standard Serial Number (ISSN)
Article - Journal
© 2016 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
01 Feb 2016