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