Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1998-01-01

Filename

WUCS-98-26.PDF

Technical Report Number

WUCS-98-26

Abstract

We study non-preemptive, online admission control in the hard deadline model: each job must be either serviced prior to its deadline, or be rejected. Our setting consists of a single resource that services an online sequence of jobs; each job has a length indicating the length of time for which it needs the resource, and a delay indicating the maximum time it can wait for the service to be started. The goal is to maximize total resource utilization. The jobs are non-preemptive and exclusive, meaning once a job begins, it runs to completion, and at most one job can use the resource at any time. We obtain a series of results, under varying assumptions of job lengths and delays, which are summarized in the following table.

Comments

Permanent URL: http://dx.doi.org/10.7936/K76H4FNP

Download

Share

COinS