TY - GEN
T1 - Mixed-criticality scheduling to minimize makespan
AU - Baruah, Sanjoy
AU - Easwaran, Arvind
AU - Guo, Zhishan
N1 - Publisher Copyright:
© Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo.
PY - 2016/12/1
Y1 - 2016/12/1
N2 - In the mixed-criticality job model, each job is characterized by two execution time parameters, representing a smaller (less conservative) estimate and a larger (more conservative) estimate on its actual, unknown, execution time. Each job is further classified as being either less critical or more critical. The desired execution semantics are that all jobs should execute correctly provided all jobs complete upon being allowed to execute for up to the smaller of their execution time estimates, whereas if some jobs need to execute beyond their smaller execution time estimates (but not beyond their larger execution time estimates), then only the jobs classified as being more critical are required to execute correctly. The scheduling of collections of such mixed-criticality jobs upon identical multiprocessor platforms in order to minimize the makespan is considered here.
AB - In the mixed-criticality job model, each job is characterized by two execution time parameters, representing a smaller (less conservative) estimate and a larger (more conservative) estimate on its actual, unknown, execution time. Each job is further classified as being either less critical or more critical. The desired execution semantics are that all jobs should execute correctly provided all jobs complete upon being allowed to execute for up to the smaller of their execution time estimates, whereas if some jobs need to execute beyond their smaller execution time estimates (but not beyond their larger execution time estimates), then only the jobs classified as being more critical are required to execute correctly. The scheduling of collections of such mixed-criticality jobs upon identical multiprocessor platforms in order to minimize the makespan is considered here.
KW - Approximation algorithm
KW - Identical parallel machines
KW - Makespan minimization
KW - Mixed criticality
KW - Scheduling
UR - https://www.scopus.com/pages/publications/85010824803
U2 - 10.4230/LIPIcs.FSTTCS.2016.7
DO - 10.4230/LIPIcs.FSTTCS.2016.7
M3 - Conference contribution
AN - SCOPUS:85010824803
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 7.1-7.13
BT - 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016
A2 - Lal, Akash
A2 - Akshay, S.
A2 - Saurabh, Saket
A2 - Sen, Sandeep
A2 - Saurabh, Saket
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016
Y2 - 13 December 2016 through 15 December 2016
ER -