Scheduling jobs with release times on a machine with finite storage

Consider a single machine with a buffer which can store up to b waiting jobs for some fixed b. Given the release times, the weights and the processing times of n consecutive jobs, a maximum weight subset of jobs is to be found that is schedulable without violating the buffer's capacity constraint. A polynomial algorithm for the unweighted loss-delay problem is presented. The weighted case is shown to be NP-hard as well as an unweighted two-machine version.