A polynomial algorithm for some preemptive multiprocessor task scheduling problems

A polynomial algorithm for some preemptive multiprocessor task scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor20084371
Country: Netherlands
Volume: 176
Issue: 1
Start Page Number: 145
End Page Number: 150
Publication Date: Jan 2007
Journal: European Journal of Operational Research
Authors: ,
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 | fixj, pmtn | ∑Cj. We give a polynomial-time algorithm to solve P | fixj, G = {P4, dart}-free, pmtn | ∑Cj problem. This result generalizes the following problems: P2 | fixj, pmtn | ∑Cj, P | |fixj| ∈ {1, m}, pmtn | ∑Cj and P4 | fixj = 2, pmtn | ∑Cj.

Reviews

Required fields are marked *. Your email address will not be published.