Improvements to the Hopfield Neural Network Solution of the TWT Scheduling Problem
  • Metaadatok
Tartalom: https://pp.bme.hu/eecs/article/view/2090
Archívum: PP Electrical Engineering and Computer Science
Gyűjtemény: Articles
Cím:
Improvements to the Hopfield Neural Network Solution of the TWT Scheduling Problem
Létrehozó:
Tornai, Kálmán; Pázmány Péter Catholic University Faculty of Information Technology
Fogarasi, Norbert; Department of Networked Systems and Services Budapest University of Technology and Economics Managing Director, Morgan Stanley Hungary Analytics
Levendovszky, János; Department of Networked Systems and Services Budapest University of Technology and Economics
Kiadó:
Budapest University of Technology and Economics (BME)
Dátum:
2013-12-10
Téma:
Scheduling, Optimization, Quadratic programming, Neural networks
Tartalmi leírás:
This paper explores novel, polynomial time, heuristic, approximate solutions to the NP-hard problem of finding the optimal job schedule on identical machines which minimizes total weighted tardiness (TWT). We map the TWT problem to quadratic optimization and demonstrate that the Hopfield Neural Network (HNN) can successfully solve it. Furthermore, the solution can be significantly sped up by choosing the initial state of the HNN as the result of a known simple heuristic, we call this Smart Hopfield Neural Network (SHNN). We also demonstrate, through extensive simulations, that by considering random perturbations to the Largest Weighted Process First (LWPF) and SHNN methods, we can introduce further improvements to the quality of the solution, we call the latter Perturbed Smart Hopfield Neural Network (PSHNN). Finally, we argue that due to parallelization techniques, such as the use of GPGPU, the additional cost of these improvements is small. Numerical simulations demonstrate that PSHNN outperforms HNN in over 99% of all randomly generated cases by an average of 3-7%, depending on the problem size. On a specific, large scale scheduling problem arising in computational finance at Morgan Stanley, one of the largest financial institutions in the world, PSHNN produced a 5% improvement over the next best heuristic.
Nyelv:
angol
Típus:
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Formátum:
application/pdf
Azonosító:
10.3311/PPee.2090
Forrás:
Periodica Polytechnica Electrical Engineering and Computer Science; Vol. 57, No. 2 (2013); 57-64
Kapcsolat:
Létrehozó:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access). As soon as the paper is accepted, finally submitted and edited, the npaper will appear in the "OnlineFirst" page of the journal, thus from this point no other internet-based publication is necessary.