1-1hit |
Tsuyoshi KAWAGUCHI Tamio TODAKA
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.