Scheduling identical jobs on uniform machines with a conflict graph

•Minimizing the makespan of scheduling identical conflicting jobs on uniform machines.•New complexity results on complete bipartite graphs with computational illustration.•Lower bounds and three MILP models to solve the problem with arbitrary graphs.•Two heuristic approaches meticulously designed to...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2019-11, Vol.111, p.357-366
Main Authors: Mallek, Amin, Bendraouche, Mohamed, Boudhar, Mourad
Format: Article
Language:English
Subjects:
Completion time
Conflict graph
Constraint modelling
Formulations
Identical jobs
Incompatible jobs
Integer programming
Job shops
Linear programming
Lower bounds
Mixed-integer linear programming
Operations research
Polynomials
Production scheduling
Schedules
Scheduling
Uniform machines
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•Minimizing the makespan of scheduling identical conflicting jobs on uniform machines.•New complexity results on complete bipartite graphs with computational illustration.•Lower bounds and three MILP models to solve the problem with arbitrary graphs.•Two heuristic approaches meticulously designed to deliver good quality solutions.•Computational experiments conducted to assess the performance of the given methods. This paper addresses the problem of scheduling n identical jobs on a set of m parallel uniform machines. The jobs are subjected to conflicting constraints modelled by an undirected graph G, in which adjacent jobs are not allowed to be processed on the same machine. Minimising the maximum completion time in the schedule (makespan Cmax) is known to be NP-hard. We prove that when G is restricted to complete bipartite graphs the problem remains NP-hard for arbitrary number of machines, however, if m is fixed an optimal solution can be obtained in polynomial time. To solve the general case of the problem, we propose mixed-integer linear programming (MILP) formulations alongside with lower bounds and heuristic approaches. Furthermore, computational experiments are carried out to measure the performance of the proposed methods.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2019.07.011