Files in this item

FilesDescriptionFormat

application/pdf

application/pdf3101970.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Scheduling Task With State -Dependent Deadlines
Author(s):Shih, Chi-Sheng
Doctoral Committee Chair(s):Jane Win-Shih Liu
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Computer Science
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.).
Issue Date:2003
Type:Text
Language:English
Description:119 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2003.
URI:http://hdl.handle.net/2142/81629
Other Identifier(s):(MiAaPQ)AAI3101970
Date Available in IDEALS:2015-09-25
Date Deposited:2003


This item appears in the following Collection(s)

Item Statistics