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.
Recommended Citation
S. K. Baruah et al., "Mixed-Criticality Scheduling to Minimize Makespan," Leibniz International Proceedings in Informatics, LIPIcs, vol. 65, pp. 7.1 - 7.13, Dagstuhl Research Online Publication Server, Dec 2016.
The definitive version is available at https://doi.org/10.4230/LIPIcs.FSTTCS.2016.7
Meeting Name
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016 (2016: Dec. 13-15, Chennai, India)
Department(s)
Computer Science
Research Center/Lab(s)
Intelligent Systems Center
Keywords and Phrases
Scheduling; Mixed criticality; Identical parallel machines; Makespan minimization; Approximation algorithm
International Standard Book Number (ISBN)
978-3-95977-027-9
International Standard Serial Number (ISSN)
1868-8969
Document Type
Article - Conference proceedings
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 2016 Sanjoy Baruah, Arvind Easwaran, and Zhishan Guo, All rights reserved.
Creative Commons Licensing
This work is licensed under a Creative Commons Attribution-Noncommercial 3.0 License
Publication Date
01 Dec 2016
