Bounds on scheduling with limited resources
- 1 January 1973
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGOPS Operating Systems Review
- Vol. 7 (4) , 104-111
- https://doi.org/10.1145/957195.808057
Abstract
A number of authors (of. [12],[6], [7],[3],[11],[4],[5],[9]) have recently been concerned with scheduling problems associated with a certain model of an abstract multiprocessing system (to be described in the next section) and, in particular, with bounds on the worst-case behavior of this system as a function of the way in which the inputs are allowed to vary. In this paper, we introduce an additional element of realism into the model by postulating the existence of a set of “resources” with the property that at no time may the system use more than some predetermined amount of each resource. With this extra constraint taken into consideration, we derive a number of bounds on the behavior of this augmented system. It will be seen that this investigation leads to several interesting results in graph theory and analysis.Keywords
This publication has 6 references indexed in Scilit:
- Optimal scheduling for two-processor systemsActa Informatica, 1972
- Erratum “Optimal Sequencing of Two Equivalent Processors”SIAM Journal on Applied Mathematics, 1971
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- Optimal Sequencing of Two Equivalent ProcessorsSIAM Journal on Applied Mathematics, 1969
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961