Scheduling multiprocessor job with resource and timing constraints using neural networks

Yueh-Min Huang, Ruey Maw Chen

Research output: Contribution to journalArticle

28 Citations (Scopus)

Abstract

The Hopfield neural network is extensively applied to obtaining an optimal/feasible solution in many different applications such as the traveling salesman problem (TSP), a typical discrete combinatorial problem. Although providing rapid convergence to the solution, TSP frequently converges to a local minimum. Stochastic simulated annealing is a highly effective means of obtaining an optimal solution capable of preventing the local minimum. This important feature is embedded into a Hopfield neural network to derive a new technique, i.e., mean field annealing. This work applies the Hopfield neural network and the normalized mean field annealing technique, respectively, to resolve a multiprocessor problem (known to be a NP-hard problem) with no process migration, constrained times (execution time and deadline) and limited resources. Simulation results demonstrate that the derived energy function works effectively for this class of problems.

Original languageEnglish
Pages (from-to)490-502
Number of pages13
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume29
Issue number4
DOIs
Publication statusPublished - 1999 Aug 1

Fingerprint

Hopfield neural networks
Traveling salesman problem
Scheduling
Neural networks
Annealing
Simulated annealing
Computational complexity

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Medicine(all)
  • Information Systems
  • Human-Computer Interaction
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this

@article{8597c354f99e4189b90cc10ff993cf42,
title = "Scheduling multiprocessor job with resource and timing constraints using neural networks",
abstract = "The Hopfield neural network is extensively applied to obtaining an optimal/feasible solution in many different applications such as the traveling salesman problem (TSP), a typical discrete combinatorial problem. Although providing rapid convergence to the solution, TSP frequently converges to a local minimum. Stochastic simulated annealing is a highly effective means of obtaining an optimal solution capable of preventing the local minimum. This important feature is embedded into a Hopfield neural network to derive a new technique, i.e., mean field annealing. This work applies the Hopfield neural network and the normalized mean field annealing technique, respectively, to resolve a multiprocessor problem (known to be a NP-hard problem) with no process migration, constrained times (execution time and deadline) and limited resources. Simulation results demonstrate that the derived energy function works effectively for this class of problems.",
author = "Yueh-Min Huang and Chen, {Ruey Maw}",
year = "1999",
month = "8",
day = "1",
doi = "10.1109/3477.775265",
language = "English",
volume = "29",
pages = "490--502",
journal = "IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics",
issn = "1083-4419",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

Scheduling multiprocessor job with resource and timing constraints using neural networks. / Huang, Yueh-Min; Chen, Ruey Maw.

In: IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, Vol. 29, No. 4, 01.08.1999, p. 490-502.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Scheduling multiprocessor job with resource and timing constraints using neural networks

AU - Huang, Yueh-Min

AU - Chen, Ruey Maw

PY - 1999/8/1

Y1 - 1999/8/1

N2 - The Hopfield neural network is extensively applied to obtaining an optimal/feasible solution in many different applications such as the traveling salesman problem (TSP), a typical discrete combinatorial problem. Although providing rapid convergence to the solution, TSP frequently converges to a local minimum. Stochastic simulated annealing is a highly effective means of obtaining an optimal solution capable of preventing the local minimum. This important feature is embedded into a Hopfield neural network to derive a new technique, i.e., mean field annealing. This work applies the Hopfield neural network and the normalized mean field annealing technique, respectively, to resolve a multiprocessor problem (known to be a NP-hard problem) with no process migration, constrained times (execution time and deadline) and limited resources. Simulation results demonstrate that the derived energy function works effectively for this class of problems.

AB - The Hopfield neural network is extensively applied to obtaining an optimal/feasible solution in many different applications such as the traveling salesman problem (TSP), a typical discrete combinatorial problem. Although providing rapid convergence to the solution, TSP frequently converges to a local minimum. Stochastic simulated annealing is a highly effective means of obtaining an optimal solution capable of preventing the local minimum. This important feature is embedded into a Hopfield neural network to derive a new technique, i.e., mean field annealing. This work applies the Hopfield neural network and the normalized mean field annealing technique, respectively, to resolve a multiprocessor problem (known to be a NP-hard problem) with no process migration, constrained times (execution time and deadline) and limited resources. Simulation results demonstrate that the derived energy function works effectively for this class of problems.

UR - http://www.scopus.com/inward/record.url?scp=0033177857&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033177857&partnerID=8YFLogxK

U2 - 10.1109/3477.775265

DO - 10.1109/3477.775265

M3 - Article

VL - 29

SP - 490

EP - 502

JO - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics

JF - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics

SN - 1083-4419

IS - 4

ER -