Scheduling multiprocessor job with resource and timing constraints using neural networks

Area of Science:

• Artificial Intelligence
• Computational Science
• Operations Research

Background:

• The Hopfield neural network is widely used for optimization problems like the traveling salesman problem (TSP).
• However, Hopfield networks often converge to local minima, limiting their effectiveness for complex optimization.
• Stochastic simulated annealing can prevent local minima but is computationally intensive.

Purpose of the Study:

• To develop a novel optimization technique by integrating the strengths of Hopfield networks and simulated annealing.
• To apply this new technique to solve a constrained multiprocessor scheduling problem, a known NP-hard problem.
• To evaluate the effectiveness of the derived energy function for this specific problem class.

Main Methods:

• The study integrates stochastic simulated annealing principles into the Hopfield neural network framework, creating a normalized mean field annealing technique.
• The Hopfield network and the normalized mean field annealing technique were applied to a multiprocessor scheduling problem.
• The problem involved constraints such as no process migration, execution time, deadlines, and limited resources.

Main Results:

• The normalized mean field annealing technique demonstrated effectiveness in resolving the multiprocessor scheduling problem.
• Simulation results validated the performance of the derived energy function for the targeted NP-hard problem.
• The integrated approach successfully navigated the complexities of constrained resource allocation.

Conclusions:

• The normalized mean field annealing technique offers a robust method for solving complex, constrained optimization problems.
• This approach enhances the capability of Hopfield networks to find optimal solutions by mitigating local minima.
• The study confirms the applicability and effectiveness of the derived energy function in multiprocessor scheduling scenarios.