A Simulated Annealing Approach to Identical Parallel Machine Scheduling
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916440328634368 |
|---|---|
| author | Li, Jiaxing Perkins, David |
| author_facet | Li, Jiaxing Perkins, David |
| contents | This paper studies the application of the simulated annealing metaheuristic on the identical parallel machine scheduling problem, a variant of the broader optimal job scheduling problem. In the identical parallel machine scheduling problem, $n$ jobs are to be assigned among $m$ machines. Furthermore, each job takes a certain amount of time that remains constant across machines. The goal of the paper is to schedule $n$ jobs on $m$ machines and minimize the maximum runtime of all machines. Both exact and heuristic methods have been applied to the problem, and the proposed algorithm falls in the heuristic category, making use of the simulated annealing metaheuristic. Compared to exact algorithms, simulated annealing was found to yield near-optimal solutions in comparable or less time for all problem cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_11880 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Simulated Annealing Approach to Identical Parallel Machine Scheduling Li, Jiaxing Perkins, David Distributed, Parallel, and Cluster Computing This paper studies the application of the simulated annealing metaheuristic on the identical parallel machine scheduling problem, a variant of the broader optimal job scheduling problem. In the identical parallel machine scheduling problem, $n$ jobs are to be assigned among $m$ machines. Furthermore, each job takes a certain amount of time that remains constant across machines. The goal of the paper is to schedule $n$ jobs on $m$ machines and minimize the maximum runtime of all machines. Both exact and heuristic methods have been applied to the problem, and the proposed algorithm falls in the heuristic category, making use of the simulated annealing metaheuristic. Compared to exact algorithms, simulated annealing was found to yield near-optimal solutions in comparable or less time for all problem cases. |
| title | A Simulated Annealing Approach to Identical Parallel Machine Scheduling |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2410.11880 |