A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts

• Published in: Computers & operations research 2021-12, Vol.136, p.105464, Article 105464
• Main Authors: Bianchessi, Nicola, Tresoldi, Emanuele
• Format: Article
• Language: English
• Subjects: Agreement graph; Algorithms; Branch-and-price; Completion time; Conflict graph; Exact solutions; Feasibility; Identical parallel machine; Job shops; Operations research; Preempting; Schedules; Scheduling
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2021.105464

•A branch-and-price algorithm for scheduling problems aiming to minimize the makespan.•The branch-and-price algorithm is competitive with state-of-the-art exact methods.•Competiveness is mainly achieved thanks to the proposed branching rules. 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.