Next: Multiprocessor Scheduling Up: Sequencing on One Processor Previous: MINIMUM SEQUENCING WITH RELEASE Index

### MINIMUM TIME-COST TRADEOFF

- 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 cj described as a step function with lj steps:

  where .
- SOLUTION: A one-processor schedule for J that obeys the precedence constraints and activities durations tj>0 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 [422].
- Comment: Variation in which for all i,j is approximable within 3/2 but not approximable within for any [422].