  The paper considers scheduling on parallel machines under the constraint that
some pairs of jobs cannot be processed concurrently. Each job has an associated
weight, and all jobs have the same deadline. The objective is to maximise the
total weight of on-time jobs. The problem is known to be strongly NP-hard in
general. A polynomial-time algorithm for scheduling unit execution time jobs on
two machines is proposed. The performance of a broad family of approximation
algorithms for scheduling unit execution time jobs on more than two machines is
analysed. For the case of arbitrary job processing times, two integer linear
programming formulations are proposed and compared with two formulations known
from the earlier literature. An iterated variable neighborhood search algorithm
is also proposed and evaluated by means of computational experiments.
