Reviving Simulated Annealing: Lifting its Degeneracies for Real-Time Job Scheduling
Files
Date
2024-01-03
Contributor
Advisor
Department
Instructor
Depositor
Speaker
Researcher
Consultant
Interviewer
Narrator
Transcriber
Annotator
Journal Title
Journal ISSN
Volume Title
Publisher
Volume
Number/Issue
Starting Page
1659
Ending Page
Alternative Title
Abstract
Inspired by the success of Simulated Annealing in physics, we transfer insights and adaptations to the scheduling domain, specifically addressing the one-stage job scheduling problem with an arbitrary number of parallel machines. In optimization, challenges arise from local optima, plateaus in the loss surface, and computationally complex Hamiltonian (cost) functions. To overcome these issues, we propose the integration of corrective actions, including symmetry breaking, restarts, and freezing out non-optimal fluctuations, into the Metropolis-Hastings algorithm. Additionally, we introduce a generalized Hamiltonian that efficiently fuses straightforward but widely applied processing-time cost functions. Our approach outperforms decision rules, meta-heuristics, and novel reinforcement learning algorithms. Notably, our method achieves these superior results in real-time, thanks to its computationally efficient evaluation of the Hamiltonian.
Description
Keywords
Simulation Modeling and Digital Twins for Decision Making in the Age of Industry 4.0, optimisation, scheduling, simulated annealing
Citation
Extent
10 pages
Format
Geographic Location
Time Period
Related To
Proceedings of the 57th Hawaii International Conference on System Sciences
Related To (URI)
Table of Contents
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International
Rights Holder
Local Contexts
Email libraryada-l@lists.hawaii.edu if you need this content in ADA-compliant format.