A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts
Articolo
Data di Pubblicazione:
2021
Citazione:
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]
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.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Agreement graph; Branch-and-price; Conflict graph; Identical parallel machine; Scheduling
Elenco autori:
N. Bianchessi, E. Tresoldi
Link alla scheda completa:
Progetto: