Augmented neural networks for task scheduling
| Autor: | Varghese S. Jacob, Anurag Agarwal, Hasan Pirkul |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Mathematical optimization
Information Systems and Management General Computer Science Artificial neural network Job shop scheduling Computational complexity theory Computer science Heuristic Management Science and Operations Research Upper and lower bounds Industrial and Manufacturing Engineering Scheduling (computing) Modeling and Simulation Heuristics |
| Zdroj: | European Journal of Operational Research. 151:481-502 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/s0377-2217(02)00605-7 |
| Popis: | We propose a new approach, called Augmented Neural Networks (AugNN) 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect