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 formulation, called Flow–Flow formulation (FFF), and its tuned version (FFT) are compared with the best existing model in the literature, a time-indexed variable formulation (F2), on benchmark instances with up to 200 jobs and 10 machines. Computational results showed that our Flow–Flow models outperformed F2 especially for instances with more than 50 jobs and optimally solved a majority of problems with 150 and 200 jobs for which F2 found only very few optimal solutions.
Efficient arc-flow formulations for makespan minimisation on parallel machines with a common server
Druetto, Alessandro;Grosso, Andrea;
In corso di stampa
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 formulation, called Flow–Flow formulation (FFF), and its tuned version (FFT) are compared with the best existing model in the literature, a time-indexed variable formulation (F2), on benchmark instances with up to 200 jobs and 10 machines. Computational results showed that our Flow–Flow models outperformed F2 especially for instances with more than 50 jobs and optimally solved a majority of problems with 150 and 200 jobs for which F2 found only very few optimal solutions.File | Dimensione | Formato | |
---|---|---|---|
postprint.pdf
Accesso aperto con embargo fino al 01/12/2027
Descrizione: POSTPRINT
Tipo di file:
POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione
777.32 kB
Formato
Adobe PDF
|
777.32 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
1-s2.0-S0305054824003836-main.pdf
Accesso riservato
Descrizione: PDF EDITORIALE
Tipo di file:
PDF EDITORIALE
Dimensione
1.82 MB
Formato
Adobe PDF
|
1.82 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.