The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Improving scheduling of tasks in a heterogeneous environment
Abstract
Optimal scheduling of parallel tasks with some precedence relationship, onto a parallel machine is known to be NP-complete. The complexity of the problem increases when task scheduling is to be done in a heterogeneous environment, where the processors in the network may not be identical and take different amounts of time to execute the same task. We introduce a task duplication-based scheduling algorithm for network of heterogeneous systems (TANH), with complexity O(V/sup 2/), which provides optimal results for applications represented by directed acyclic graphs (DAGs), provided a simple set of conditions on task computation and network communication time could be satisfied. The performance of the algorithm is illustrated by comparing the scheduling time with an existing "best imaginary level scheduling (BIL)" scheme for heterogeneous systems. The scalability for a higher or lower number of processors, as per their availability is also discussed. We have shown to provide substantial improvement over existing work on the task duplication-based scheduling algorithm (TDS).
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70356-x · Cited by 5,854
A taxonomy of scheduling in general-purpose distributed computing systems
Casavant, T. L., & Kuhl, J. G. (1988) · IEEE Transactions on Software Engineering · doi:10.1109/32.4634 · Cited by 976
Cited by
Workflow Scheduling Algorithms for Grid Computing
Yu, J., Buyya, R., & Ramamohanarao, K. (2008) · Studies in Computational Intelligence · doi:10.1007/978-3-540-69277-5_7 · Cited by 388
Helix: Serving Large Language Models over Heterogeneous GPUs and Network via Max-Flow
Mei, Y., Zhuang, Y., Miao, X., Yang, J., Jia, Z., & Vinayak, R. (2025) · Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1 · doi:10.1145/3669940.3707215 · Cited by 35
Metadata
- Authors
- Bajaj, R., & Agrawal, D. P.
- Venue
- IEEE Transactions on Parallel and Distributed Systems
- Published
- 2004-02
- Volume
- 15
- Issue
- 2
- Pages
- 107-118
- ISSN
- 1045-9219 (ISSN-L)
- OpenAlex
- W2114719509
- Cited by
- 283
- References
- 3
- FWCI
- 16.50
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Improving scheduling of tasks in a heterogeneous environment. https://app.cochat.ai/papers/10.1109/tpds.2004.1264795
- The paper
- Bajaj, R., & Agrawal, D. P. (2004). Improving scheduling of tasks in a heterogeneous environment. IEEE Transactions on Parallel and Distributed Systems. https://doi.org/10.1109/tpds.2004.1264795
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.