Resource scheduling for parallel database and scientific applications

Soumen Chakrabarti; S. Muthukrishnan

doi:10.1145/237502.237577

Resource scheduling for parallel database and scientific applications

Soumen Chakrabarti, S. Muthukrishnan

Research output: Contribution to conference › Paper › peer-review

Abstract

Scheduling problems that are critical and prevalent in practical parallel computing are computed. A polynomial time makespan algorithm that produces a schedule of length O(V+Φ log T), which is therefore an O(log T) approximation is presented to solve these problems. The makespan algorithm can be extended to minimize the weighted average completion time over all the jobs to the same approximation factor of O(log T).

Original language	English (US)
Pages	329-335
Number of pages	7
DOIs	https://doi.org/10.1145/237502.237577
State	Published - 1996
Event	Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures - Padua, Italy Duration: Jun 24 1996 → Jun 26 1996

Other

Other	Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures
City	Padua, Italy
Period	6/24/96 → 6/26/96

ASJC Scopus subject areas

Software
Safety, Risk, Reliability and Quality

Access to Document

10.1145/237502.237577

Cite this

@conference{47de4affd7ab49ff85070e84abf0a409,

title = "Resource scheduling for parallel database and scientific applications",

abstract = "Scheduling problems that are critical and prevalent in practical parallel computing are computed. A polynomial time makespan algorithm that produces a schedule of length O(V+Φ log T), which is therefore an O(log T) approximation is presented to solve these problems. The makespan algorithm can be extended to minimize the weighted average completion time over all the jobs to the same approximation factor of O(log T).",

author = "Soumen Chakrabarti and S. Muthukrishnan",

year = "1996",

doi = "10.1145/237502.237577",

language = "English (US)",

pages = "329--335",

note = "Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures ; Conference date: 24-06-1996 Through 26-06-1996",

}

TY - CONF

T1 - Resource scheduling for parallel database and scientific applications

AU - Chakrabarti, Soumen

AU - Muthukrishnan, S.

PY - 1996

Y1 - 1996

N2 - Scheduling problems that are critical and prevalent in practical parallel computing are computed. A polynomial time makespan algorithm that produces a schedule of length O(V+Φ log T), which is therefore an O(log T) approximation is presented to solve these problems. The makespan algorithm can be extended to minimize the weighted average completion time over all the jobs to the same approximation factor of O(log T).

AB - Scheduling problems that are critical and prevalent in practical parallel computing are computed. A polynomial time makespan algorithm that produces a schedule of length O(V+Φ log T), which is therefore an O(log T) approximation is presented to solve these problems. The makespan algorithm can be extended to minimize the weighted average completion time over all the jobs to the same approximation factor of O(log T).

UR - http://www.scopus.com/inward/record.url?scp=0030398638&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030398638&partnerID=8YFLogxK

U2 - 10.1145/237502.237577

DO - 10.1145/237502.237577

M3 - Paper

AN - SCOPUS:0030398638

SP - 329

EP - 335

T2 - Proceedings of the 1996 8th Annual ACM Symposium on Parallel Algorithms and Architectures

Y2 - 24 June 1996 through 26 June 1996

ER -

Resource scheduling for parallel database and scientific applications

Abstract

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this