A polynomial algorithm for some preemptive multiprocessor task scheduling problems

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.07.022 Byline: Aukasz Kuszner, MichaA MaAafiejski Keywords: Scheduling; Complexity theory; Multiprocessor tasks; Dedicated processors Abstract: 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 a[pounds sterling]fix.sub.j , pmtna[pounds sterling]aC.sub.j . We give a polynomial-time algorithm to solve P a[pounds sterling]fix.sub.j , G ={P.sub.4,dart}-free, pmtna[pounds sterling]aC.sub.j problem. This result generalizes the following problems: P2a[pounds sterling]fix.sub.j , pmtna[pounds sterling]aC.sub.j , P a[pounds sterling]a[pounds sterling]fix.sub.j a[pounds sterling][member of]{1, m}, pmtna[pounds sterling]aC.sub.j and P4a[pounds sterling]fix.sub.j =2, pmtna[pounds sterling]aC.sub.j . Author Affiliation: Department of Algorithms and System Modeling, Gdansk University of Technology, Narutowicza 11/12, 80-952 Gdansk, Poland Article History: Received 10 May 2004; Accepted 6 July 2005