A polynomial algorithm for some preemptive multiprocessor task scheduling problems

In this paper we consider a problem of preemptive scheduling of multiprocessor tasks on dedicated processors in order to minimize the sum of completion times. Using a standard notation, our problem can be denoted as P ∣ fix_j, pmtn ∣ ∑C_j. We give a polynomial-time algorithm to solve P ∣ fix_j, G = {P₄, dart}-free, pmtn ∣ ∑C_j problem. This result generalizes the following problems: P2 ∣ fix_j, pmtn ∣ ∑C_j, P ∣ ∣fix_j∣ ∈ {1, m}, pmtn ∣ ∑C_j and P4 ∣ fix_j = 2, pmtn ∣ ∑C_j.