- INSTANCE:
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 with steps:

where . - SOLUTION:
A one-processor schedule for
*J*that obeys the precedence constraints and activities durations for each that obeys the budget, i.e. . - MEASURE:
The total duration of all activities, i.e.,
.

*Good News:*Approximable within , where*f*is the ratio of the maximum allowed duration of any activity to the minimum allowed non-zero duration of any activity [445].*Comment:*Variation in which for all*i,j*is approximable within 3/2 but not approximable within for any [445].