Next: MINIMUM STORAGE-TIME SEQUENCING
Up: Sequencing on One Processor
Previous: Sequencing on One Processor
  Index
- 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
Viggo Kann
2000-03-20