SCHEDULING JOBS WITH RELEASE TIMES ON A MACHINE WITH FINITE STORAGE

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