Abstract
Given a set ofn tasks andm resources, where each taskx has a rational weightx.w=x.e/x.p,0<x.w<1, aperiodic schedule is one that allocates a resource to a taskx for exactlyx.e time units in each interval [x.p·k, x.p·(k+1)) for allk∈N. We define a notion of proportionate progress, called P-fairness, and use it to design an efficient algorithm which solves the periodic scheduling problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. K. Baruah, R. R. Howell, and L. E. Rosier. Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor.Real-Time Systems, 2:301–324, 1990.
M. Blum, R. W. Floyd, V. R. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection.Journal of Computer and System Sciences, 7:448–461, 1973.
X. Deng. Mathematical Programming: Complexity and Applications. Ph.D. thesis, Department of Operations Research, Stanford University, Stanford, CA, September 1989.
L. R. Ford, Jr., and D. R. Fulkerson.Flows in Networks. Princeton University Press, Princeton, NJ, 1962.
M. R. Garey and D. S. Johnson.Computers and Intractability.A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.
D. S. Hirschberg and C. K. Wong. A polynomial-time algorithm for the knapsack problem with two variables.Journal of the Association for Computing Machinery, 23:147–154, 1976.
W. A. Horn. Some simple scheduling algorithms.Naval Research Logistics Quarterly, 21:177–185, 1974.
R. Kannan. A polynomial algorithm for the two-variable integer programming problem.Journal of the Association for Computing Machinery, 27:118–122, 1980.
H. W. Lenstra, Jr. Integer programming with a fixed number of variables.Mathematics of Operations Research, 8:538–548, 1983.
J. Y.-T. Leung. A new algorithm for scheduling periodic, real-time tasks.Algorithmica, 4:209–219, 1989.
C. L. Liu. Scheduling Algorithms for Multiprocessors in a Hard-Real-Time Environment. JPL Space Programs Summary 37–60, vol. II, Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA, pages 28–37, November, 1969.
C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment.Journal of the Association for Computing Machinery, 20:46–61, 1973.
H. E. Scarf. Production sets with indivisibilities, Part I: Generalities.Econometrica, 49:1–32, 1981.
H. E. Scarf. Production sets with indivisibilities, Part II: The case of two activities.Econometrica, 49:395–423, 1981.
Author information
Authors and Affiliations
Additional information
Communicated by C. L. Lui.
This research was supported by NSF Research Initiation Award CCR-9111591, and the Texas Advanced Research Program under Grant No. 91-003658-480.
Rights and permissions
About this article
Cite this article
Baruah, S.K., Cohen, N.K., Plaxton, C.G. et al. Proportionate progress: A notion of fairness in resource allocation. Algorithmica 15, 600–625 (1996). https://doi.org/10.1007/BF01940883
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01940883