Multi-Constraint Job Scheduling by Clustering Scheme of Fuzzy Neural Network

Ruey-Maw CHEN  Yueh-Min HUANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E84-D   No.3   pp.384-393
Publication Date: 2001/03/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Biocybernetics, Neurocomputing
Keyword: 
scheduling,  fuzzy c-means clustering,  Hopfield neural network,  fuzzy Hopfield neural network,  

Full Text: PDF>>
Buy this Article




Summary: 
Most scheduling applications have been classified into NP-complete problems. This fact implies that an optimal solution for a large scheduling problem is extremely time-consuming. A number of schemes are introduced to solve NP-complete scheduling applications, such as linear programming, neural network, and fuzzy logic. In this paper, we demonstrate a new approach, fuzzy Hopfield neural network, to solve the scheduling problems. This fuzzy Hopfield neural network approach integrates fuzzy c-means clustering strategies into a Hopfield neural network. In this investigation, we utilizes this new approach to demonstrate the feasibility of resolving a multiprocessor scheduling problem with no process migration, limited resources and constrained times (execution time and deadline). In the approach, the process and processor of the scheduling problem can be regarded as a data sample and a cluster, respectively. Then, an appropriate Lyapunov energy function is derived correspondingly. The scheduling results can be obtained using a fuzzy Hopfield neural network clustering technique by iteratively updating fuzzy state until the energy function gets minimized. To validate our approach, three scheduling cases for different initial neuron states as well as fuzzification parameters are taken as testbed. Simulation results reveal that imposing the fuzzy Hopfield neural network on the proposed energy function provides a sound approach in solving this class of scheduling problems.