Technical Report Number
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.
Goldman, Sally A.; Parwatikar, Jyoti; and Suri, Subhash, "On-line Scheduling with Hard Deadlines" Report Number: WUCS-98-26 (1998). All Computer Science and Engineering Research.