Augmented neural networks for task scheduling

Augmented neural networks for task scheduling

0.00 Avg rating0 Votes
Article ID: iaor20043087
Country: Netherlands
Volume: 151
Issue: 3
Start Page Number: 481
End Page Number: 502
Publication Date: Dec 2003
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics, neural networks
Abstract:

We propose a new approach, called Augmented Neural Networks (Aug NN) for solving the task-scheduling problem. This approach is a hybrid of the heuristic and the neural networks approaches. While retaining all the advantages of the heuristic approach, AugNN incorporates learning, to find improved solutions iteratively. This new framework maps the problem structure to a neural network and utilizes domain specific knowledge for finding solutions. The problem we address is that of minimizing the makespan in scheduling n tasks on m machines where the tasks follow a precedence relation and task pre-emption is not allowed. Solutions obtained from AugNN using various learning rules are compared with six different commonly used heuristics. AugNN approach provides significant improvements over heuristic results. In just a few iterations, the gap between the lower bound and the obtained solution is reduced by as much as 58% for some heuristics, without any increase in computational complexity. While the heuristics found solutions in the range of 5.8–26.9% of the lower bound, on average, AugNN found solutions in the range of 3.3–11.1%, a significant improvement.

Reviews

Required fields are marked *. Your email address will not be published.