Operation Scheduling by Annealed Neural Networks

Tsuyoshi KAWAGUCHI  Tamio TODAKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.6   pp.656-663
Publication Date: 1995/06/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Papers Selected from 1994 Joint Technical Conference on Circuits/Systems, Computers and Communications (JTC-CSCC '94))
neural networks,  scheduling,  optimization,  

Full Text: PDF(612.4KB)>>
Buy this Article

The operation scheduling is an important subtask in the automatic synthesis of digital systems. Many greedy heuristics have been proposed for the operation scheduling, but they cannot find the globally best schedule. In this paper we present an algorithm to construct near optimal schedules. The algorithm combines characteristics of simulated annealing and neural networks. The neural network used in our scheduling algorithm is similar to that proposed by Hellstrom et al. However, while the problems of Refs. [11] and [12] have a single type of constraint, the problem considered in this paper has three types of constraints. As the result, the energy function of the proposed neural network is given by the weighted sum of three energy functions. To minimize the weighted sum of two or more energy functions, conventional methods try to find a good set of weights using a try and error method. Our algorithm takes a different approach than these methods. Results of the experiments show that the proposed algorithm can be used as an alternative heuristic for solving the operation scheduling problem. In addition, the proposed algorithm can exploit the inherent parallelism of the neural network.