Article ID: | iaor20172818 |
Volume: | 20 |
Issue: | 4 |
Start Page Number: | 355 |
End Page Number: | 372 |
Publication Date: | Aug 2017 |
Journal: | Journal of Scheduling |
Authors: | Leus Roel, Kowalczyk Daniel |
Keywords: | manufacturing industries, scheduling, combinatorial optimization, heuristics |
We consider an extension of classic parallel machine scheduling where a set of jobs is scheduled on identical parallel machines and an undirected conflict graph is part of the input. Each node in the graph represents a job, and an edge implies that its two jobs are conflicting, meaning that they cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time (makespan) is minimized. We present an exact algorithm based on branch and price that combines methods from bin packing, scheduling, and graph coloring, with appropriate modifications. The algorithm has a good computational performance even for parallel machine scheduling without conflicting jobs.