Deadline Scheduling Problems

Overview

In practice, a large delay of completion is not acceptable for every job.
Therefore, a customer may assign a deadline to his job. In the Infrastructure-as-a-Service business model of cloud computing, system providers rent out infrastructure (typically but not limited to computing power) to customers. They are responsible for system management and resource allocation.

Deadline scheduling is very important for mid-size providers with limited available resources, since in large installation there exist enough back-up resources to complete all jobs on time.

Current work

We consider a basic admission control problem in which jobs with deadlines arrive online and our goal is to maximize the total volume of executed job processing times. We assume that for every job, there is a minimum amount of scheduling flexibility defined by slack. In addition, we require the admission policy to support immediate commitment, that is, upon a job’s submission, we must immediately make the decision of if and where we schedule the job, and this decision is irreversible.