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 vertical bar fix(j), pmtn vertical bar Sigma C-j. We give a polynomial-time algorithm to solve P vertical bar fix(j), G = {P-4,dart}-free, pmtn vertical bar Sigma C-j problem. This result generalizes the following problems: P2 vertical bar fix(j), pmtn vertical bar Sigma C-j, P vertical bar vertical bar fix(j)vertical bar is an element of {1,m}, pmtn vertical bar Sigma C-j and P4 vertical bar fix(j) = 2, pmtn vertical bar Sigma C-j. (c) 2005 Elsevier B.V. All rights reserved.