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.

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

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

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial 3.0 License

Share

 
COinS