We consider the problem of scheduling n jobs with differ- ent processing times on parallel identical machines with job incompatibility constraints and preemption possibil- ity. Three objectives have to be minimized in lexicograph- ical (or hierarchical) order: makespan, number of job in- terruptions, and sum of throughput times over all jobs. A linear programming formulation, a greedy heuristic and a tabu search are proposed to solve this problem.