Next: MINIMUM STORAGE-TIME SEQUENCING Up: Sequencing on One Processor Previous: Sequencing on One Processor Index

### MAXIMUM CONSTRAINED SEQUENCING TO MINIMIZE TARDY TASK WEIGHT

- 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 [452].

- Garey and Johnson: Similar to SS3