SS1 MAXIMUM CONSTRAINED SEQUENCING TO MINIMIZE TARDY TASK WEIGHT

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

I NSTANCE : Set T of tasks, for each task a length , a weight , and a deadline , a subset , and a positive integer K .
S OLUTION : A one-processor schedule for T such that the sum of w(t) , taken over all for which does not exceed K .
M EASURE : Cardinality of jobs in S completed by the deadline.
Bad News: Not approximable within for some [ 352 ].
Garey and Johnson: Similar to SS3

Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997