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

Area of Science:

• Computer Science
• Operations Research
• Artificial Intelligence

Background:

• Real-time scheduling problems often involve complex objectives like piecewise linear utility functions.
• Existing methods may struggle with efficiency and scalability for these problems.

Purpose of the Study:

• To develop an efficient and scalable method for solving real-time scheduling problems with piecewise linear objectives.
• To leverage neural networks for optimizing scheduling tasks.

Main Methods:

• Transformation of scheduling problems into linear constraint optimization using approximation schemes and matrix vectorization.
• Application of a parallel, circuit-implementable neural network for efficient optimization.
• Development of an algorithm with a guaranteed approximation ratio bound of 0.5.

Main Results:

• The neural network model demonstrates efficient convergence, suitable for real-time requirements.
• Experimental results show the algorithm is optimal for non-overloaded sets and outperforms existing strategies for overloaded sets.
• Solution time remains stable regardless of problem size (number of jobs).

Conclusions:

• The proposed neural network-based optimization method provides an efficient solution for real-time scheduling problems with piecewise linear utility functions.
• The approach is scalable and robust, performing well even under heavy system loads.
• This method has broad applicability in areas like mixed criticality, response time minimization, and tardiness analysis.