  Machine scheduling problems involving conflict jobs can be seen as a
constrained version of the classical scheduling problem, in which some jobs are
conflict in the sense that they cannot be proceeded simultaneously on different
machines. This conflict constraint naturally arises in several practical
applications and has recently received considerable attentions in the research
community. In fact, the problem is typically NP-hard (even for approximation)
and most of algorithmic results achieved so far have heavily relied on special
structures of the underlying graph used to model the conflict-job relation. Our
focus is on three objective functions: minimizing the makespan, minimizing the
weighted summation of the jobs' completion time, and maximizing the total
weights of completed jobs; the first two of which have been intensively studied
in the literature. For each objective function considered, we present several
mixed integer linear programming models and a constraint programming model,
from which we can solve the problems to optimality using dedicated solvers.
Binary search-based algorithms are also proposed to solve the makespan problem.
The results of numerical experiments performed on randomly generated data sets
with up to 32 jobs and 6 machines are reported and analysed to verify the
performance of the proposed methods.
