- INSTANCE:
Set
*T*of tasks, for each task a length , a weight , and a deadline , a subset , and a positive integer*K*. - SOLUTION:
A one-processor schedule
for
*T*such that the sum of*w(t)*, taken over all for which does not exceed*K*. - MEASURE:
Cardinality of jobs in
*S*completed by the deadline.

*Bad News:*Not approximable within for some [476].*Garey and Johnson:*Similar to SS3