Split-Proof Probabilistic Scheduling

Herve Moulin

Working Papers from Rice University, Department of Economics

Abstract: If shortest jobs are served first, splitting a long job into smaller jobs reported under different aliases can reduce the actual wait until completion. If longest jobs are served first, the dual maneuver of merging several jobs under a single reported identity is profitable. Both manipulations can be avoided if the scheduling order is random, and users care only about the expected wait until completion of their job. The Proportional rule stands out among rules immune to splitting and merging. It draws the job served last with probabilities proportional to size, then repeats among the remaining jobs. Among split-proof scheduling rules constructed in this recursive way, it is characterized by either one of the three following properties: an agent with a longer job incurs a longer delay; total expected delay is at most twice optimal delay; the worst expected delay of any single job is at most twice the smallest feasible worst delay. A similar result holds within the natural family of separable rules.

Date: 2005-03
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.ruf.rice.edu/~econ/papers/2005papers/prosched19.pdf

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ecl:riceco:2004-06

Access Statistics for this paper

More papers in Working Papers from Rice University, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by ().