Efficient arc-flow formulations for makespan minimisation on parallel machines with a common server
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- General variable neighborhood search for the parallel machine scheduling problem with two common serversOptimization Letters, 2022
- A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common serverComputers & Operations Research, 2019
- Preemptive parallel‐machine scheduling with a common server to minimize makespanNaval Research Logistics (NRL), 2017
- Modeling and solving static m identical parallel machines scheduling problem with a common server and sequence dependent setup timesComputers & Industrial Engineering, 2017
- Bin packing and related problems: General arc-flow formulation with graph compressionComputers & Operations Research, 2016
- MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single serverComputers & Operations Research, 2012
- Parallel dedicated machine scheduling problem with sequence-dependent setups and a single serverComputers & Industrial Engineering, 2010
- The feasibility pumpMathematical Programming, 2005
- Exploring relaxation induced neighborhoods to improve MIP solutionsMathematical Programming, 2004
- Scheduling two parallel semiautomatic machines to minimize machine interferenceComputers & Operations Research, 1996