2002/12/09 by Tei‐Wei Kuo, Aloysius K. Mok · 2 citations
Computer Science · Mathematics · #Real-Time Systems Scheduling #Petri Nets in System Modeling #Formal Methods in Verification #Scalability #Computer science #Set (abstract data type) #Upper and lower bounds #Mathematical optimization #Process (computing) #Selection (genetic algorithm) #Scheduling (production processes) #Algorithm #Mathematics #Artificial intelligence
paper · doi:10.1109/real.1991.160369
openalex publication_date 2002/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
A framework is given for discussing how to adjust load in order to handle periodic processes whose timing parameters vary with time. The schedulability of adjustable periodic processes by a preemptive fixed priority scheduler is formulated in terms of a configuration selection problem. Specifically, two process transformations are introduced for the purpose of deriving a bound for the achievable utilization factor of processes whose periods are related by harmonics. This result is then generalized so that the bound is applicable to any process set and an efficient algorithm to calculate the bound is provided. When the list of allowable configurations is implicitly given by a set of scalable periodic processes, the corresponding period assignment problem is shown to be NP-complete. The authors present an approximation algorithm for the period assignment problem for which some encouraging experimental results are included.>