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 $j\in J$ a non-increasing cost function $c_j$ described as a step function with $l_j$ steps:
  
  $$c_j(t)=\left\{\begin{array}{ll} \infty&\mbox{if $0\le t< a_{j... ...le i<l_j$},\\ 0&\mbox{if $a_{j,l_j}\le t$}, \end{array}\right.$$
  
  
  where $\infty>c_j(a_{j,1})>\cdots>c_j(a_{j,l_j})$.
• SOLUTION: A one-processor schedule for J that obeys the precedence constraints and activities durations $t_j>0$ for each $j\in J$ that obeys the budget, i.e. $\sum_{j\in J} c_j(t_j)\le B$.
• MEASURE: The total duration of all activities, i.e., $\sum_{j\in J} t_j$.

  
  

• Good News: Approximable within $(3/2)\log f+(7/2)$, 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 $a_{j,i}\in\{0,1,2\}$ for all i,j is approximable within 3/2 but not approximable within $3/2-\varepsilon$ for any $\varepsilon >0$ [445].