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.
Agreement graph; Branch-and-price; Conflict graph; Identical parallel machine; Scheduling
Settore MAT/09 - Ricerca Operativa
Settore INF/01 - Informatica
   Advanced Cosmetic Manifacturing (AD-COM)
   AD-COM
   REGIONE LOMBARDIA
   ID 214632
2021
Article (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/884756
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact