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.
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
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016 (2016: Dec. 13-15, Chennai, India)
Keywords and Phrases
Scheduling; Mixed criticality; Identical parallel machines; Makespan minimization; Approximation algorithm
International Standard Book Number (ISBN)
International Standard Serial Number (ISSN)
Article - Conference proceedings
© 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