Compact formulations and valid inequalities for parallel machine scheduling with conflicts

The problem of scheduling conflicting jobs on parallel machines consists in assigning a set of jobs to a set of machines so that no two conflicting jobs are allocated to the same machine, and the maximum processing time among all machines is minimized. We propose a new compact mixed integer linear f...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-07
Main Authors: Moura, Phablo F S, Leus, Roel, Yaman, Hande
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Enumeration
Graph theory
Graphical representations
Inequalities
Integer programming
Linear programming
Mixed integer
Polytopes
Scheduling
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of scheduling conflicting jobs on parallel machines consists in assigning a set of jobs to a set of machines so that no two conflicting jobs are allocated to the same machine, and the maximum processing time among all machines is minimized. We propose a new compact mixed integer linear formulation based on the representatives model for the vertex coloring problem, which overcomes a number of issues inherent in the natural assignment model. We present a polyhedral study of the associated polytope, and describe classes of valid inequalities inherited from the stable set polytope. We describe branch-and-cut algorithms for the problem, and report on computational experiments with benchmark instances. Our computational results on the hardest instances of the benchmark set show that the proposed algorithms are superior (either in running time or quality of the solutions) to the current state-of-the-art methods. We find that our new method performs better than the existing ones especially when the gap between the optimal value and the trivial lower bound (i.e., the sum of all processing times divided by the number of machines) increases.
ISSN:2331-8422