Allocation and scheduling of precedence- and timing-constrained tasks with communication delays

Bo Chao Cheng; Alexander D. Stoyenko; Thomas J. Marlowe; Sanjoy Baruah

Allocation and scheduling of precedence- and timing-constrained tasks with communication delays

Bo Chao Cheng
, Alexander D. Stoyenko
, Thomas J. Marlowe
, Sanjoy Baruah

Department of Computer Science & Engineering

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

1 Scopus citations

Abstract

The problem of non-preemptively scheduling a set of n tasks on m identical processors with communication overhead subject to precedence and deadline constraints considered. A new heuristic with the time complexity of O(n²m), Least Space-Time First (LSTF), is proposed to minimize the maximum tardiness. From simulation results, it is shown that LSTF outperforms other heuristic algorithms.

Original language	English
Pages	91-94
Number of pages	4
State	Published - 1996
Event	Proceedings of the 1996 2nd IEEE International Conference on Engineering of Complex Computer Systems - Montreal, Can Duration: Oct 21 1996 → Oct 25 1996

Conference

Conference	Proceedings of the 1996 2nd IEEE International Conference on Engineering of Complex Computer Systems
City	Montreal, Can
Period	10/21/96 → 10/25/96

Cite this

@conference{8b8abda3888d4e78bb5052072146fa94,

title = "Allocation and scheduling of precedence- and timing-constrained tasks with communication delays",

abstract = "The problem of non-preemptively scheduling a set of n tasks on m identical processors with communication overhead subject to precedence and deadline constraints considered. A new heuristic with the time complexity of O(n2m), Least Space-Time First (LSTF), is proposed to minimize the maximum tardiness. From simulation results, it is shown that LSTF outperforms other heuristic algorithms.",

author = "Cheng, \{Bo Chao\} and Stoyenko, \{Alexander D.\} and Marlowe, \{Thomas J.\} and Sanjoy Baruah",

year = "1996",

language = "English",

pages = "91--94",

note = "Proceedings of the 1996 2nd IEEE International Conference on Engineering of Complex Computer Systems ; Conference date: 21-10-1996 Through 25-10-1996",

}

Allocation and scheduling of precedence- and timing-constrained tasks with communication delays. / Cheng, Bo Chao; Stoyenko, Alexander D.; Marlowe, Thomas J. et al.
1996. 91-94 Paper presented at Proceedings of the 1996 2nd IEEE International Conference on Engineering of Complex Computer Systems, Montreal, Can.

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

TY - CONF

T1 - Allocation and scheduling of precedence- and timing-constrained tasks with communication delays

AU - Cheng, Bo Chao

AU - Stoyenko, Alexander D.

AU - Marlowe, Thomas J.

AU - Baruah, Sanjoy

PY - 1996

Y1 - 1996

N2 - The problem of non-preemptively scheduling a set of n tasks on m identical processors with communication overhead subject to precedence and deadline constraints considered. A new heuristic with the time complexity of O(n2m), Least Space-Time First (LSTF), is proposed to minimize the maximum tardiness. From simulation results, it is shown that LSTF outperforms other heuristic algorithms.

AB - The problem of non-preemptively scheduling a set of n tasks on m identical processors with communication overhead subject to precedence and deadline constraints considered. A new heuristic with the time complexity of O(n2m), Least Space-Time First (LSTF), is proposed to minimize the maximum tardiness. From simulation results, it is shown that LSTF outperforms other heuristic algorithms.

UR - https://www.scopus.com/pages/publications/0030401224

M3 - Paper

AN - SCOPUS:0030401224

SP - 91

EP - 94

T2 - Proceedings of the 1996 2nd IEEE International Conference on Engineering of Complex Computer Systems

Y2 - 21 October 1996 through 25 October 1996

ER -

Allocation and scheduling of precedence- and timing-constrained tasks with communication delays

Abstract

Conference

Other files and links

Fingerprint

Cite this