We consider a scheduling problem where a set of n jobs has to be processed in a non-preemptive way on a set of m identical parallel machines. Each job j is associated with a positive integer processing time pj. The problem is also characterized by a conflict graph where adjacent nodes in the graph represent conflicting jobs that cannot be processed on the same machine. A schedule is an assignment of a time interval of pj time units on m machines for each job j. The schedule is feasible if intervals on the same machine do not overlap, and jobs to be processed on the same machine are pairwise not conflicting. The aim is to find a feasible schedule that minimizes the maximum completion time of the jobs. The problem is NP-hard as it generalizes both the problem of scheduling jobs on identical parallel machines to the aim of minimizing the makespan (P||Cmax) and the vertex coloring problem (VCP), two well-known NP-hard problems. We present the first stand-alone branch-and-price (BP) algorithm that works directly on the problem. In comprehensive computational experiments with benchmark instances, we prove that the new BP algorithm, even without using ad hoc primal heuristics and feasibility check algorithms, is competitive with the best exact solution algorithm proposed so far in the literature. These results are mainly achieved thanks to the branching scheme we propose.
A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts / N. Bianchessi, E. Tresoldi. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 136:(2021), pp. 105464.1-105464.13. [10.1016/j.cor.2021.105464]
A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts
N. Bianchessi
Primo
;E. Tresoldi
2021
Abstract
We consider a scheduling problem where a set of n jobs has to be processed in a non-preemptive way on a set of m identical parallel machines. Each job j is associated with a positive integer processing time pj. The problem is also characterized by a conflict graph where adjacent nodes in the graph represent conflicting jobs that cannot be processed on the same machine. A schedule is an assignment of a time interval of pj time units on m machines for each job j. The schedule is feasible if intervals on the same machine do not overlap, and jobs to be processed on the same machine are pairwise not conflicting. The aim is to find a feasible schedule that minimizes the maximum completion time of the jobs. The problem is NP-hard as it generalizes both the problem of scheduling jobs on identical parallel machines to the aim of minimizing the makespan (P||Cmax) and the vertex coloring problem (VCP), two well-known NP-hard problems. We present the first stand-alone branch-and-price (BP) algorithm that works directly on the problem. In comprehensive computational experiments with benchmark instances, we prove that the new BP algorithm, even without using ad hoc primal heuristics and feasibility check algorithms, is competitive with the best exact solution algorithm proposed so far in the literature. These results are mainly achieved thanks to the branching scheme we propose.File | Dimensione | Formato | |
---|---|---|---|
main-ALL.pdf
Open Access dal 21/06/2024
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
413.28 kB
Formato
Adobe PDF
|
413.28 kB | Adobe PDF | Visualizza/Apri |
1-s2.0-S030505482100215X-main.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
738.32 kB
Formato
Adobe PDF
|
738.32 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.