Online scheduling with hard deadlines

We study non-preemptive, online admission control in the hard deadline mode l: each job must either be serviced prior to its deadline or be rejected. O ur setting consists of a single resource that services an online sequence o f jobs; each job has a length indicating the length of time for which it ne eds the resource and a delay indicating the maximum time it can wait for th e 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 fan use the resource at any time. W e obtain a series of results, under varying assumptions of job lengths and delays. (C) 2000 Academic Press.