Set J of activities, a directed acyclic graph defining precedence
constraints for the activities, a positive budget B, and for each activity
a non-increasing cost function
described as a step function
A one-processor schedule for J that obeys the precedence constraints and
that obeys the budget, i.e.
The total duration of all activities, i.e.,
where f is the ratio of the maximum
allowed duration of any activity to the minimum allowed non-zero duration of
any activity .
Variation in which
for all i,j is approximable within
3/2 but not approximable within