@inproceedings{d406484cb7934b96a10fa04cb85cfd37,
title = "Fixed-Priority Schedulability of Sporadic Tasks on Uniprocessors is NP-Hard",
abstract = "We study the computational complexity of the FP-schedulability problem for sporadic or synchronous periodic tasks on a preemptive uniprocessor. We show that this problem is (weakly) NP-hard, even when restricted to either (i) task sets with implicit deadlines and rate-monotonic priority ordering, or (ii) task sets with constrained deadlines, deadline-monotonic priority ordering and utilization bounded by any constant c, such that 0 c 1.",
keywords = "Scheduling, complexity, fixed-priority, real-time",
author = "Pontus Ekberg and Wang Yi",
note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 38th IEEE Real-Time Systems Symposium, RTSS 2017 ; Conference date: 05-10-2017 Through 08-10-2017",
year = "2017",
month = jul,
day = "2",
doi = "10.1109/RTSS.2017.00020",
language = "英语",
series = "Proceedings - Real-Time Systems Symposium",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "139--146",
booktitle = "Proceedings - 2017 IEEE Real-Time Systems Symposium, RTSS 2017",
address = "美国",
}