SS4 M INIMUM S EQUENCING WITH R ELEASE T IMES

   
• I NSTANCE : Set T of tasks, for each task a release time , a length , and a weight .
• S OLUTION : A one-processor schedule for T that obeys the release times, i.e. a function such that, for all , if S(u) is the set of tasks t for which , then |S(u)| = 1 and for each task t , .
• M EASURE : The weighted sum of completion times, i.e. .

• Good News: Approximable within 2 [ 132 ].
• Comment: Approximable within if all weights w(t)=1 [ 65 ]. Variation in which there are precedence constraints on T instead of release times is approximable within 2 [ 146 ].