2014/09/08 by Krishnendu Chatterjee, Chatterjee, Krishnendu, Andreas Pavlogiannis +5 · 1 voice
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #FOS: Electrical engineering #Optimization and Search Problems #Scheduling and Optimization Algorithms #Systems and Control (eess.SY) #cs.DS #eess.SY #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1409.2291
openalex publication_date 2014/09/08 · arxiv published 2014/09/08 · arxiv updated 2014/09/14 · openalex created_date 2022/10/04 · openalex updated_date 2026/08/01
We present a flexible framework for the automated competitive analysis of\non-line scheduling algorithms for firm-deadline real-time tasks based on\nmulti-objective graphs: Given a taskset and an on-line scheduling algorithm\nspecified as a labeled transition system, along with some optional safety,\nliveness, and/or limit-average constraints for the adversary, we automatically\ncompute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler.\nWe demonstrate the flexibility and power of our approach by comparing the\ncompetitive ratio of several on-line algorithms, including Dover, that\nhave been proposed in the past, for various tasksets. Our experimental results\nreveal that none of these algorithms is universally optimal, in the sense that\nthere are tasksets where other schedulers provide better performance. Our\nframework is hence a very useful design tool for selecting optimal algorithms\nfor a given application.\n