Miklos Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, and Orli Waarts. Fairness in scheduling. Journal of Algorithms 29(2):306–357, November, 1998. (SODA 1995 special issue.) An earlier version appeared in Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1995, pp. 477–485.
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 living processes which should be repeatedly scheduled for various tasks throughout the lifetime of a system. For any such instance we develop a notion of desired load of a process, which is a function of the tasks it participates in. The unfairness of 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 the carpool problem suggested by Fagin and Williams. In this problem, a set of n people 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.
@article(AjtaiANRSW1998,
title="Fairness in scheduling",
author="Miklos Ajtai and James Aspnes and Moni Naor and Yuval Rabani and Leonard J. Schulman and Orli Waarts",
journal={Journal of Algorithms},
volume=29,
number=2,
pages={306--357},
month=nov,
year=1998
)