We consider a parallel machine scheduling problem with incompatibilities, and preemptions. Furthermore, a global deadline is given, and make it impossible to perform all the jobs. Two objectives are considered, the first is to maximize the gains of the completely performed jobs, the second is to minimize the number of required machines. Five approaches are proposed: a greedy algorithm, a descent local search, a tabu search, a tabu search with restarts, and a deconstruction-reconstruction metaheuristic. The results show the efficiency of the deconstruction-reconstruction metaheuristic.