Minimum Loss Scheduling

Nawijn, W. M. and Kern, Walter and Baas, S. M. (1990) Minimum Loss Scheduling.
Technical Report , 30 p.


Consider a single machine with buffer of capacity one for waiting jobs. Given the arrival epochs, the weights and the processing times of n consecutive future 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. For the weighted one-machine case, shown to be NP-hard, a dynamic programming formulation is given.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr90-082
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 09 Jan 2012 11:48