An exact algorithm for parallel machine scheduling with conflicts

An exact algorithm for parallel machine scheduling with conflicts

0.00 Avg rating0 Votes
Article ID: iaor20172818
Volume: 20
Issue: 4
Start Page Number: 355
End Page Number: 372
Publication Date: Aug 2017
Journal: Journal of Scheduling
Authors: ,
Keywords: manufacturing industries, scheduling, combinatorial optimization, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.