{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72067"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72067","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scheduling Real-Time Computations With Temporal Distance and Separation Constraints and With Extended Deadlines","abstract":"In hard real-time systems, computations not only must be functionally correct but also must meet their strict timing constraints. To guarantee the timing requirements are satisfied, effective scheduling algorithms must be used. Different real-time applications have different timing requirements. Therefore, different timing constraints must be defined for different real-time applications. Also, different scheduling algorithms need to be designed for different real-time systems to effectively and efficiently schedule the computations to meet their timing constraints. We propose new real-time scheduling problems to model real-time systems in which computations have relative timing constraints. For relative timing constraints, we mean that a computation's ready time or deadline is relative to the actual start time (or finishing time) of some other computation. The Job Scheduling with Distance Constraints problem requires certain pairs of jobs to be scheduled within some given distance of each other. The Job Scheduling with Separation Constraints problem requires two related jobs to be scheduled no smaller than the separation constraint between them. We analyze the scheduling problems with these kinds of relative timing constraints and design several scheduling algorithms for some of them. We also propose new real-time scheduling problems to model real-time systems in which computations have more than one deadline. In the Scheduling with Extended Deadline problem, computations can be delayed after their first (primary) deadlines but must be finished before their second (extended) deadlines. We study two variations of this problem. In the first model, the system receives a penalty for each computation that does not finish its execution before its primary deadline. In the second model, there is an extra overhead for each computation that can not be finished before its primary deadline. We discuss the scheduling issues of the problems under these two models and design some algorithms for scheduling real-time computations with extended deadlines.","abstract_html":"In hard real-time systems, computations not only must be functionally correct but also must meet their strict timing constraints. To guarantee the timing requirements are satisfied, effective scheduling algorithms must be used. Different real-time applications have different timing requirements. Therefore, different timing constraints must be defined for different real-time applications. Also, different scheduling algorithms need to be designed for different real-time systems to effectively and efficiently schedule the computations to meet their timing constraints. We propose new real-time scheduling problems to model real-time systems in which computations have relative timing constraints. For relative timing constraints, we mean that a computation's ready time or deadline is relative to the actual start time (or finishing time) of some other computation. The Job Scheduling with Distance Constraints problem requires certain pairs of jobs to be scheduled within some given distance of each other. The Job Scheduling with Separation Constraints problem requires two related jobs to be scheduled no smaller than the separation constraint between them. We analyze the scheduling problems with these kinds of relative timing constraints and design several scheduling algorithms for some of them. We also propose new real-time scheduling problems to model real-time systems in which computations have more than one deadline. In the Scheduling with Extended Deadline problem, computations can be delayed after their first (primary) deadlines but must be finished before their second (extended) deadlines. We study two variations of this problem. In the first model, the system receives a penalty for each computation that does not finish its execution before its primary deadline. In the second model, there is an extra overhead for each computation that can not be finished before its primary deadline. We discuss the scheduling issues of the problems under these two models and design some algorithms for scheduling real-time computations with extended deadlines.","abstract_has_math":false,"creators":["Han, Ching-Chih"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Lin, Kwei-Jay"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T20:00:26Z","date_published":"2014-12-17T20:00:26Z","updated_at":"2026-07-22T22:26:06Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9305546"],"render_values":[{"text":"(UMI)AAI9305546","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72067","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lin, Kwei-Jay"]},{"key":"dc:creator","label":"Author","values":["Han, Ching-Chih"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T20:00:26Z","10000-01-01","1992"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72067","(UMI)AAI9305546"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In hard real-time systems, computations not only must be functionally correct but also must meet their strict timing constraints. To guarantee the timing requirements are satisfied, effective scheduling algorithms must be used. Different real-time applications have different timing requirements. Therefore, different timing constraints must be defined for different real-time applications. Also, different scheduling algorithms need to be designed for different real-time systems to effectively and efficiently schedule the computations to meet their timing constraints. We propose new real-time scheduling problems to model real-time systems in which computations have relative timing constraints. For relative timing constraints, we mean that a computation's ready time or deadline is relative to the actual start time (or finishing time) of some other computation. The Job Scheduling with Distance Constraints problem requires certain pairs of jobs to be scheduled within some given distance of each other. The Job Scheduling with Separation Constraints problem requires two related jobs to be scheduled no smaller than the separation constraint between them. We analyze the scheduling problems with these kinds of relative timing constraints and design several scheduling algorithms for some of them. We also propose new real-time scheduling problems to model real-time systems in which computations have more than one deadline. In the Scheduling with Extended Deadline problem, computations can be delayed after their first (primary) deadlines but must be finished before their second (extended) deadlines. We study two variations of this problem. In the first model, the system receives a penalty for each computation that does not finish its execution before its primary deadline. In the second model, there is an extra overhead for each computation that can not be finished before its primary deadline. We discuss the scheduling issues of the problems under these two models and design some algorithms for scheduling real-time computations with extended deadlines.","Made available in DSpace on 2014-12-17T20:00:26Z (GMT). No. of bitstreams: 1 9305546.pdf: 5233733 bytes, checksum: dfa689c0a8c6a3c1b3e815c5be0b8212 (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72235 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","113 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."]},{"key":"dc:title","label":"Title","values":["Scheduling Real-Time Computations With Temporal Distance and Separation Constraints and With Extended Deadlines"]}]}],"canonical_facts":{"dc:contributor":["Lin, Kwei-Jay"],"dc:creator":["Han, Ching-Chih"],"dc:date":["2014-12-17T20:00:26Z","10000-01-01","1992"],"dc:description":["In hard real-time systems, computations not only must be functionally correct but also must meet their strict timing constraints. To guarantee the timing requirements are satisfied, effective scheduling algorithms must be used. Different real-time applications have different timing requirements. Therefore, different timing constraints must be defined for different real-time applications. Also, different scheduling algorithms need to be designed for different real-time systems to effectively and efficiently schedule the computations to meet their timing constraints. We propose new real-time scheduling problems to model real-time systems in which computations have relative timing constraints. For relative timing constraints, we mean that a computation's ready time or deadline is relative to the actual start time (or finishing time) of some other computation. The Job Scheduling with Distance Constraints problem requires certain pairs of jobs to be scheduled within some given distance of each other. The Job Scheduling with Separation Constraints problem requires two related jobs to be scheduled no smaller than the separation constraint between them. We analyze the scheduling problems with these kinds of relative timing constraints and design several scheduling algorithms for some of them. We also propose new real-time scheduling problems to model real-time systems in which computations have more than one deadline. In the Scheduling with Extended Deadline problem, computations can be delayed after their first (primary) deadlines but must be finished before their second (extended) deadlines. We study two variations of this problem. In the first model, the system receives a penalty for each computation that does not finish its execution before its primary deadline. In the second model, there is an extra overhead for each computation that can not be finished before its primary deadline. We discuss the scheduling issues of the problems under these two models and design some algorithms for scheduling real-time computations with extended deadlines.","Made available in DSpace on 2014-12-17T20:00:26Z (GMT). No. of bitstreams: 1 9305546.pdf: 5233733 bytes, checksum: dfa689c0a8c6a3c1b3e815c5be0b8212 (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72235 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","113 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."],"dc:identifier":["http://hdl.handle.net/2142/72067","(UMI)AAI9305546"],"dc:subject":["Computer Science"],"dc:title":["Scheduling Real-Time Computations With Temporal Distance and Separation Constraints and With Extended Deadlines"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:06Z"}