Mixed-criticality scheduling to minimize makespan

Sanjoy Baruah; Arvind Easwaran; Zhishan Guo

doi:10.4230/LIPIcs.FSTTCS.2016.7

Mixed-criticality scheduling to minimize makespan

Sanjoy Baruah, Arvind Easwaran, Zhishan Guo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016
Editors	Akash Lal, S. Akshay, Saket Saurabh, Sandeep Sen, Saket Saurabh
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	7.1-7.13
ISBN (Electronic)	9783959770279
DOIs	https://doi.org/10.4230/LIPIcs.FSTTCS.2016.7
Publication status	Published - Dec 1 2016
Externally published	Yes
Event	36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016 - Chennai, India Duration: Dec 13 2016 → Dec 15 2016

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	65
ISSN (Print)	1868-8969

Conference

Conference	36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016
Country/Territory	India
City	Chennai
Period	12/13/16 → 12/15/16

Bibliographical note

Publisher Copyright:
© Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo.

ASJC Scopus Subject Areas

Software

Keywords

Approximation algorithm
Identical parallel machines
Makespan minimization
Mixed criticality
Scheduling

Access to Document

10.4230/LIPIcs.FSTTCS.2016.7

Cite this

Baruah, S., Easwaran, A., & Guo, Z. (2016). Mixed-criticality scheduling to minimize makespan. In A. Lal, S. Akshay, S. Saurabh, S. Sen, & S. Saurabh (Eds.), 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016 (pp. 7.1-7.13). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 65). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.FSTTCS.2016.7

Baruah, Sanjoy ; Easwaran, Arvind ; Guo, Zhishan. / Mixed-criticality scheduling to minimize makespan. 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016. editor / Akash Lal ; S. Akshay ; Saket Saurabh ; Sandeep Sen ; Saket Saurabh. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. pp. 7.1-7.13 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{a649adabd37a4426bdb975b49031192a,

title = "Mixed-criticality scheduling to minimize makespan",

abstract = "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.",

keywords = "Approximation algorithm, Identical parallel machines, Makespan minimization, Mixed criticality, Scheduling",

author = "Sanjoy Baruah and Arvind Easwaran and Zhishan Guo",

note = "Publisher Copyright: {\textcopyright} Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo.; 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016 ; Conference date: 13-12-2016 Through 15-12-2016",

year = "2016",

month = dec,

day = "1",

doi = "10.4230/LIPIcs.FSTTCS.2016.7",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "7.1--7.13",

editor = "Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen and Saket Saurabh",

booktitle = "36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016",

}

Baruah, S, Easwaran, A & Guo, Z 2016, Mixed-criticality scheduling to minimize makespan. in A Lal, S Akshay, S Saurabh, S Sen & S Saurabh (eds), 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016. Leibniz International Proceedings in Informatics, LIPIcs, vol. 65, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 7.1-7.13, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, Chennai, India, 12/13/16. https://doi.org/10.4230/LIPIcs.FSTTCS.2016.7

Mixed-criticality scheduling to minimize makespan. / Baruah, Sanjoy; Easwaran, Arvind; Guo, Zhishan.
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016. ed. / Akash Lal; S. Akshay; Saket Saurabh; Sandeep Sen; Saket Saurabh. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. p. 7.1-7.13 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 65).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 - http://www.scopus.com/inward/record.url?scp=85010824803&partnerID=8YFLogxK

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

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 -

Baruah S, Easwaran A, Guo Z. Mixed-criticality scheduling to minimize makespan. In Lal A, Akshay S, Saurabh S, Sen S, Saurabh S, editors, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. p. 7.1-7.13. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.FSTTCS.2016.7

Mixed-criticality scheduling to minimize makespan

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this