Technical Report CS0790

TR#:CS0790
Class:CS
Title: MINIMIZING THE FLOW TIME FOR PARALLELIZABLE TASK SYSTEMS (PRELIMINARY VERSION).
Authors: J. Glasgow and H. Shachnai
PDFNot Available
Abstract:

Consider the problem of scheduling tasks on a multiprocessor where each task can be parallelized to run simultaneously on several processors. The number of processors assigned to the execution of a task is chosen at runtime. In general, increasing the number of processors assigned to a task will decrease its execution time. Our objective is to schedule the tasks so as to minimize the mean flow time (MFT), also known as the average response time of the system. We show that this problem is NP-hard in the strong sense. For scenarios in which the runtime per task decreases linearly with the number of processors allotted to it, we present the Sorted Earliest Completion Time (SECT) heuristic. SECT is shown to achieve a worst case bound of 3 to the MFT of the optimal schedule in time O(n \log n+nm), where m is the number of processors, and n is the number of tasks.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1993/CS/CS0790), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1993
To the main CS technical reports page

Computer science department, Technion
admin