Fairness in Scheduling |
| |
| Authors: | Miklos Ajtai James Aspnes Moni Naor Yuval Rabani Leonard J Schulman Orli Waarts |
| |
| Affiliation: | aIBM Research Division, Almaden Research Center, San Jose, California;bDepartment of Computer Science, Yale University, New Haven, Connecticut, 06520-8285;cDepartment of Applied Mathematics and Computer Science, Weizmann Institute, Israel;dICSI, Berkeley, California;eLaboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts;fComputer Science Division, University of California, Berkeley, California |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
