This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/81629
Description
Title
Scheduling Task With State -Dependent Deadlines
Author(s)
Shih, Chi-Sheng
Issue Date
2003
Doctoral Committee Chair(s)
Jane Win-Shih Liu
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
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.).
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
