We consider a job-scheduling problem arising
on cloud systems and in broadcasting networks,
where the goal is to optimally utilize a limited amount
of a resource (e.g., cloud servers, bandwidth, or storage
capacity) available along a given time interval. The
resource is utilized by a set of weighted jobs. The
processing of a job consists of several contiguous stages,
each having a specific length and a specific resourcedemand,
such that the set of demands forms a decreasing
sequence. Each job is associated with a release time
and a deadline, defining the time interval in which it
can be processed. Some notable applications for this
scenario include progressive download, QuickStart and
prefetching methods, hierarchical image reconstruction,
and routine security and maintenance tasks. The goal is
to find a feasible schedule of a maximum-weight subset
of the jobs. In a feasible schedule, at any time, the total
amount of resource allocated to the active jobs does not
exceed the available amount of resource.
Since this problem is NP-hard already for highly
restricted inputs, we focus on obtaining approximation algorithms
and heuristics and present a comparative study
among them. Our main result, the first constant-factor
approximation algorithm for the problem, generalizes the
state of art for the fundamental problem of resource
constrained real-time scheduling, to scenarios where jobs
may have dwindling resource requirements. Our empirical
study shows that this algorithm is in fact nearly optimal
for realistic inputs.