Efficient arc-flow formulations for makespan minimisation on parallel machines with a common server

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 the same set of nodes representing points in time, and arcs associated with job execution, and with machines or server idleness. The resulting formulation and its tuned version are compared with the best existing model in the literature, a time-indexed variable formulation, on benchmark instances with up to 200 jobs and 7 machines.

 Computational results showed that our models outperformed the other one for instances with 100 jobs and produced optimal solutions to the vast majority of problems with 150 and 200 jobs, for which the other model 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.