Scheduling for Minimum Total Loss Using Service Time Distributions
- 1 January 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 21 (1), 66-75
- https://doi.org/10.1145/321796.321803
Abstract
An analytic model of a single processor scheduling problem is investigated. The scheduling objective is to minimize the total loss incurred by a finite number of initially available requests when each request has an associated linear loss function. The assumptions of the model are that preemption is allowed with negligible loss of processor time, and that the distribution of actual service times is known for each class of requests. A request is associated with a class by any of its characteristics except its actual service time. A contrived example demonstrates that one reasonable scheduling rule does not always minimize expected total loss. The major results of the paper are the definition of a new scheduling rule based on the known service time distributions, and the proof that expected total loss is always minimized by using this new rule. Brief consideration is given to generalizations of the model in which new requests arrive randomly, and preemption requires a non-negligible amount of processor time.Keywords
This publication has 6 references indexed in Scilit:
- Use of service time distributions in schedulingPublished by Office of Scientific and Technical Information (OSTI) ,1971
- A note on time sharing with preferred customersProbability Theory and Related Fields, 1968
- Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time DisciplineOperations Research, 1968
- The Priority Problem and Computer Time SharingManagement Science, 1966
- Scheduling with Random Service TimesManagement Science, 1966
- Scheduling with Deadlines and Loss FunctionsManagement Science, 1959