Fairness in Scheduling
Open accessAbstract
On-line machine scheduling has been studied extensively, but the fundamental issue of fairness in scheduling is still mostly open. In this paper we explore the issue in settings where there are long-lived processes which should be repeatedly scheduled for various tasks throughout the lifetime of a system. For any such instance we develop a notion ofdesiredload of a process, which is a function of the tasks it participates in. Theunfairnessof a system is the maximum, taken over all processes, of the difference between the desired load and the actual load. An example of such a setting is thecarpool problemsuggested by Fagin and Williams [IBM Journal of Research and Development27(2) (1983), 133–139]. In this problem, a set ofnpeople form a carpool. On each day a subset of the people arrive and one of them is designated as the driver. A scheduling rule is required so that the driver will be determined in a “fair” way. We investigate this problem under various assumptions on the input distribution. We also show that the carpool problems can capture several other problems of fairness in scheduling.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The carpooling problem was first proposed and studied in Fagin and Williams (1983) and later studied in Ajtai et al. (1998).
“From the point of view of algorithm, the carpooling problem was first proposed and studied in Fagin and Williams (1983) and later studied in Ajtai et al. (1998).”
From PoliUniPool: a carpooling system for universities (2011) · cites this paper as Ajtai et al. (1998)
Ajtai et al. (1998) and Fagin and Williams (1983) mostly deal with online schemes, where the schedule of future arrivals of participants is not known.
“Ajtai et al. (1998) and Fagin and Williams (1983), for the most part, deal with online schemes, i.e. when the schedule of future arrivals of participants is not known.”
From PoliUniPool: a carpooling system for universities (2011) · cites this paper as Ajtai et al. (1998)
Cites
Analysis and simulation of a fair queueing algorithm
Demers, A. J., Keshav, S., & Shenker, S. J. (1989) · ACM SIGCOMM Computer Communication Review · doi:10.1145/75247.75248 · Cited by 2,616 · see citing works
Amortized efficiency of list update and paging rules
Sleator, D. D., & Tarjan, R. E. (1985) · Communications of the ACM · doi:10.1145/2786.2793 · Cited by 2,123 · see citing works
Bounds for Certain Multiprocessing Anomalies
Graham, R. (1966) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1966.tb01709.x · Cited by 1,661 · see citing works
High-speed switch scheduling for local-area networks
Anderson, T. E., Owicki, S. S., Saxe, J. B., et al. (1993) · ACM Transactions on Computer Systems · doi:10.1145/161541.161736 · Cited by 894 · see citing works
Bloch, E. D. (2003) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4612-2130-2_6 · Cited by 372 · see citing works
A binary feedback scheme for congestion avoidance in computer networks
Ramakrishnan, K. K., & Jain, R. K. (1990) · ACM Transactions on Computer Systems · doi:10.1145/78952.78955 · Cited by 365 · see citing works
Round-robin scheduling for max-min fairness in data networks
Hahne, E. L. (1991) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.103550 · Cited by 357 · see citing works
Beck, J., & Fiala, T. (1981) · Discrete Applied Mathematics · doi:10.1016/0166-218x(81)90022-6 · Cited by 234 · see citing works
Algorithms for Scheduling Tasks on Unrelated Processors
Davis, E., & Jaffe, J. M. (1981) · Journal of the ACM · doi:10.1145/322276.322284 · Cited by 146 · see citing works
An Algorithm for Rate Allocation in a Packet-Switching Network With Feedback
Charny, A. (1994) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 119 · see citing works
The chairman assignment problem
Tijdeman, R. (1980) · Discrete Mathematics · doi:10.1016/0012-365x(80)90269-1 · Cited by 98 · see citing works
A fair carpool scheduling algorithm
Fagin, R., & Williams, J. H. (1983) · IBM Journal of Research and Development · doi:10.1147/rd.272.0133 · Cited by 73 · see citing works
Disks, Balls, and Walls: Analysis of a Combinatorial Game
Anderson, R., Lovász, L., Shor, P., et al. (1989) · American Mathematical Monthly · doi:10.1080/00029890.1989.11972227 · Cited by 18 · see citing works
Balanced two-colorings of finite sets in the cube
Beck, J. (1988) · Discrete Mathematics · doi:10.1016/0012-365x(88)90129-x · Cited by 10 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., & Zemel, R. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090255 · Cited by 3,501 · see citing works
PoliUniPool: a carpooling system for universities
Bruglieri, M., Ciccarelli, D., Colorni, A., & Luè, A. (2011) · Procedia - Social and Behavioral Sciences · doi:10.1016/j.sbspro.2011.08.062 · Cited by 66 · see citing works
“Ajtai et al. (1998) and Fagin and Williams (1983), for the most part, deal with online schemes, i.”
BackgroundMethodInfluential
- Authors
- Ajtai, M., Aspnes, J., Naor, M., Rabani, Y., Schulman, L. J., & Waarts, O.
- Affiliations
- Yale University (US)
- Weizmann Institute of Science (IL)
- International Computer Science Institute (US)
- University of California, Berkeley (US)
- Venue
- Journal of Algorithms
- Publisher
- Elsevier BV
- Published
- 1998-11
- Volume
- 29
- Issue
- 2
- Pages
- 306-357
- ISSN
- 0196-6774 (ISSN-L)
- OpenAlex
- W4236693084
- Cited by
- 47
- References
- 14
- Citations by year
- 2025: 4 · 2024: 3 · 2023: 1 · 2022: 1 · 2021: 3 · 2020: 2 · 2018: 1 · 2017: 2 · 2016: 1 · 2015: 2 · 2014: 3 · 2013: 1 · 2012: 2
- FWCI
- 2.57
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Journal of Algorithms (publishedVersion, cc-by-nc-nd)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Optimization and Search Problems
- Social Sciences › Economics, Econometrics and Finance › Economics and Econometrics › Game Theory and Voting Systems
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Scheduling and Optimization Algorithms
- Keywords
- unfairness, driver selection, input distribution, load balancing
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
