--- _id: '5423' abstract: - lang: eng text: 'We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application. ' alternative_title: - IST Austria Technical Report author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Alexander full_name: Kössler, Alexander last_name: Kössler - first_name: Andreas full_name: Pavlogiannis, Andreas id: 49704004-F248-11E8-B48F-1D18A9856A87 last_name: Pavlogiannis orcid: 0000-0002-8943-0722 - first_name: Ulrich full_name: Schmid, Ulrich last_name: Schmid citation: ama: Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks. IST Austria; 2014. doi:10.15479/AT:IST-2014-300-v1-1 apa: Chatterjee, K., Kössler, A., Pavlogiannis, A., & Schmid, U. (2014). A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. IST Austria. https://doi.org/10.15479/AT:IST-2014-300-v1-1 chicago: Chatterjee, Krishnendu, Alexander Kössler, Andreas Pavlogiannis, and Ulrich Schmid. A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-300-v1-1. ieee: K. Chatterjee, A. Kössler, A. Pavlogiannis, and U. Schmid, A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks. IST Austria, 2014. ista: Chatterjee K, Kössler A, Pavlogiannis A, Schmid U. 2014. A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks, IST Austria, 14p. mla: Chatterjee, Krishnendu, et al. A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks. IST Austria, 2014, doi:10.15479/AT:IST-2014-300-v1-1. short: K. Chatterjee, A. Kössler, A. Pavlogiannis, U. Schmid, A Framework for Automated Competitive Analysis of On-Line Scheduling of Firm-Deadline Tasks, IST Austria, 2014. date_created: 2018-12-12T11:39:15Z date_published: 2014-07-29T00:00:00Z date_updated: 2023-02-23T10:11:15Z day: '29' ddc: - '005' department: - _id: KrCh doi: 10.15479/AT:IST-2014-300-v1-1 file: - access_level: open_access checksum: 4b8fde4d9ef6653837f6803921d83032 content_type: application/pdf creator: system date_created: 2018-12-12T11:53:53Z date_updated: 2020-07-14T12:46:50Z file_id: '5514' file_name: IST-2014-300-v1+1_main.pdf file_size: 1270021 relation: main_file file_date_updated: 2020-07-14T12:46:50Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '14' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '300' related_material: record: - id: '1714' relation: later_version status: public status: public title: A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ...