Preemptive scheduling with finite capacity input buffers

Preemptive scheduling with finite capacity input buffers

0.00 Avg rating0 Votes
Article ID: iaor19972320
Country: Netherlands
Volume: 70
Issue: 1
Start Page Number: 399
End Page Number: 413
Publication Date: Apr 1997
Journal: Annals of Operations Research
Authors: , ,
Abstract:

In many scheduling problems, an arriving job is stored in an input buffer until it starts to be processed. Also, it may be necessary to hold a partially completed preempted job in an input buffer until processing of this job resumes. In the scheduling literature, most problems have been studied using the implicit assumption that the buffer capacity is finite. In this scheduling environment, jobs may be lost either because of insufficient input buffer capacity, or because due date requirements cannot be met. The authors examine problems where the objective is to minimize the weighted or unweighted number of lost jobs. Various assumptions about the generality of the data are examined. The authors present a complexity classification for various problems, either by deriving an efficient algorithm, or by proving that such an algorithm is unlikely to exist.

Reviews

Required fields are marked *. Your email address will not be published.