{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/81629"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/81629","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scheduling Task With State -Dependent Deadlines","abstract":"This thesis then considers the general case when a job may have more than one feasible interval. Such a job is constrained to execute from start to completion in one of its feasible intervals. The problem of meeting the timing constraint of such jobs is divided into three problems: feasible interval determination, feasible interval selection, and job scheduling. When the deadline of every job is given as a known time function, there is an optimal feasible interval determination algorithm: The algorithm determines the start times and end times of feasible intervals of every job so that the job will never miss its deadline if the job executes from start to completion in one of its feasible intervals. When the future values of job deadlines are unknown, it is not possible to make optimal determination of feasible intervals. We developed several algorithms to determine probabilistically feasible interval start times and end times for each job so that the probability of a job meeting its timing constraint is no less than a given threshold if it executes from start to completion in one of its feasible intervals. Given the start times and end times of feasible intervals, the problem of selecting a feasible interval for each job in a set of multiple feasible interval jobs so that all jobs complete in time is NP-hard. The optimal branch-and-bound algorithm described here can be used when there is time to compute the schedule. (Abstract shortened by UMI.).","abstract_html":"This thesis then considers the general case when a job may have more than one feasible interval. Such a job is constrained to execute from start to completion in one of its feasible intervals. The problem of meeting the timing constraint of such jobs is divided into three problems: feasible interval determination, feasible interval selection, and job scheduling. When the deadline of every job is given as a known time function, there is an optimal feasible interval determination algorithm: The algorithm determines the start times and end times of feasible intervals of every job so that the job will never miss its deadline if the job executes from start to completion in one of its feasible intervals. When the future values of job deadlines are unknown, it is not possible to make optimal determination of feasible intervals. We developed several algorithms to determine probabilistically feasible interval start times and end times for each job so that the probability of a job meeting its timing constraint is no less than a given threshold if it executes from start to completion in one of its feasible intervals. Given the start times and end times of feasible intervals, the problem of selecting a feasible interval for each job in a set of multiple feasible interval jobs so that all jobs complete in time is NP-hard. The optimal branch-and-bound algorithm described here can be used when there is time to compute the schedule. (Abstract shortened by UMI.).","abstract_has_math":false,"creators":["Shih, Chi-Sheng"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Jane Win-Shih Liu"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-25T20:19:36Z","date_published":"2015-09-25T20:19:36Z","updated_at":"2026-07-22T22:26:16Z","subjects":["Computer Science"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI3101970"],"render_values":[{"text":"(MiAaPQ)AAI3101970","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/81629","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Jane Win-Shih Liu"]},{"key":"dc:creator","label":"Author","values":["Shih, Chi-Sheng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-25T20:19:36Z","10000-01-01","2003"]},{"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":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/81629","(MiAaPQ)AAI3101970"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["This thesis then considers the general case when a job may have more than one feasible interval. Such a job is constrained to execute from start to completion in one of its feasible intervals. The problem of meeting the timing constraint of such jobs is divided into three problems: feasible interval determination, feasible interval selection, and job scheduling. When the deadline of every job is given as a known time function, there is an optimal feasible interval determination algorithm: The algorithm determines the start times and end times of feasible intervals of every job so that the job will never miss its deadline if the job executes from start to completion in one of its feasible intervals. When the future values of job deadlines are unknown, it is not possible to make optimal determination of feasible intervals. We developed several algorithms to determine probabilistically feasible interval start times and end times for each job so that the probability of a job meeting its timing constraint is no less than a given threshold if it executes from start to completion in one of its feasible intervals. Given the start times and end times of feasible intervals, the problem of selecting a feasible interval for each job in a set of multiple feasible interval jobs so that all jobs complete in time is NP-hard. The optimal branch-and-bound algorithm described here can be used when there is time to compute the schedule. (Abstract shortened by UMI.).","Made available in DSpace on 2015-09-25T20:19:36Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3101970.pdf: 5812090 bytes, checksum: 9055bd0a6b6c955cb4895bb5a9be5b1d (MD5) Previous issue date: 2003","Embargo set by: Seth Robbins for item 82910 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","119 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2003."]},{"key":"dc:title","label":"Title","values":["Scheduling Task With State -Dependent Deadlines"]}]}],"canonical_facts":{"dc:contributor":["Jane Win-Shih Liu"],"dc:creator":["Shih, Chi-Sheng"],"dc:date":["2015-09-25T20:19:36Z","10000-01-01","2003"],"dc:description":["This thesis then considers the general case when a job may have more than one feasible interval. Such a job is constrained to execute from start to completion in one of its feasible intervals. The problem of meeting the timing constraint of such jobs is divided into three problems: feasible interval determination, feasible interval selection, and job scheduling. When the deadline of every job is given as a known time function, there is an optimal feasible interval determination algorithm: The algorithm determines the start times and end times of feasible intervals of every job so that the job will never miss its deadline if the job executes from start to completion in one of its feasible intervals. When the future values of job deadlines are unknown, it is not possible to make optimal determination of feasible intervals. We developed several algorithms to determine probabilistically feasible interval start times and end times for each job so that the probability of a job meeting its timing constraint is no less than a given threshold if it executes from start to completion in one of its feasible intervals. Given the start times and end times of feasible intervals, the problem of selecting a feasible interval for each job in a set of multiple feasible interval jobs so that all jobs complete in time is NP-hard. The optimal branch-and-bound algorithm described here can be used when there is time to compute the schedule. (Abstract shortened by UMI.).","Made available in DSpace on 2015-09-25T20:19:36Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3101970.pdf: 5812090 bytes, checksum: 9055bd0a6b6c955cb4895bb5a9be5b1d (MD5) Previous issue date: 2003","Embargo set by: Seth Robbins for item 82910 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","119 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2003."],"dc:identifier":["http://hdl.handle.net/2142/81629","(MiAaPQ)AAI3101970"],"dc:language":["eng"],"dc:subject":["Computer Science"],"dc:title":["Scheduling Task With State -Dependent 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:16Z"}