A Neurodynamic Approach for Real-Time Scheduling via Maximizing Piecewise Linear Utility

Abstract

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.

Department(s)

Computer Science

Research Center/Lab(s)

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)

2162-237X

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2016 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Feb 2016

Link to Full Text

Share

 
COinS