Efficient arc-flow formulations for makespan minimisation on parallel machines with a common server
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918173742202880 |
|---|---|
| author | Druetto, Alessandro Grosso, Andrea Jeunet, Jully Salassa, Fabio |
| author_facet | Druetto, Alessandro Grosso, Andrea Jeunet, Jully Salassa, Fabio |
| contents | We consider the problem of scheduling non preemptively a set of jobs on parallel identical machines with prior setup operations on a single shared server, where the objective is to minimise the makespan. We develop an arc-flow formulation to the problem with two multigraphs, one for the machines and one for the server, with a same set of nodes representing points in time, and arcs associated with job execution, and with machines or server idleness. The resulting Flow-Flow formulation (FFF) and its tuned version (FFT) are compared with the best existing model in the literature, TIV I, on benchmark instances with up to 200 jobs and 7 machines. Computational results showed that our Flow-Flow models outperformed TIV I for instances with 100 jobs and produced optimal solutions to the vast majority of problems with 150 and 200 jobs for which TIV I failed to even find integer solutions within the standard limited runtime of 3600 s. When non optimal, solutions provided by our models exhibited very low gaps to best bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08629 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient arc-flow formulations for makespan minimisation on parallel machines with a common server Druetto, Alessandro Grosso, Andrea Jeunet, Jully Salassa, Fabio Optimization and Control 90C27 (Primary) 90C11 (Secondary) We consider the problem of scheduling non preemptively a set of jobs on parallel identical machines with prior setup operations on a single shared server, where the objective is to minimise the makespan. We develop an arc-flow formulation to the problem with two multigraphs, one for the machines and one for the server, with a same set of nodes representing points in time, and arcs associated with job execution, and with machines or server idleness. The resulting Flow-Flow formulation (FFF) and its tuned version (FFT) are compared with the best existing model in the literature, TIV I, on benchmark instances with up to 200 jobs and 7 machines. Computational results showed that our Flow-Flow models outperformed TIV I for instances with 100 jobs and produced optimal solutions to the vast majority of problems with 150 and 200 jobs for which TIV I failed to even find integer solutions within the standard limited runtime of 3600 s. When non optimal, solutions provided by our models exhibited very low gaps to best bound. |
| title | Efficient arc-flow formulations for makespan minimisation on parallel machines with a common server |
| topic | Optimization and Control 90C27 (Primary) 90C11 (Secondary) |
| url | https://arxiv.org/abs/2402.08629 |