Incentives and General Welfare Functions in the Off-Line
Cluster Scheduling Problem
Orna Agmon's Research Thesis Seminar for the degree of master of science
in applied mathematics. The research thesis was done under the supervision of
Dr. Rann. Smorordinsky in the department of industrial engineering.
The seminar will take place on
Time: Wed., Jan 15, 10:30-11:30.
Place: Bloomfield 424, Technion
Lecture slides in pdf and ps.
The whole thesis, in pdf
Abstract
Several agents wish to execute one job each on a cluster- several
computers which are a resource owned by an institution. The job's
length is a secret known to the agent alone, and the agent's utility
is the negation of the time in which she gets the output of the
job. The institution would like to maximize a
social welfare function over the agents' utilities by scheduling the
jobs on the various computers. For example, the institution may wish
to minimize the sum of times in which the agents get the output from
their jobs, or to minimize the output time of the last job to come.
The problem is that it cannot schedule the jobs thus, because
it does not know the jobs' lengths.
We construct mechanisms in which the
agents prefer to tell the institution the real length of their
jobs, while the institution maximizes a general social welfare
function.
Those mechanisms involve both monetary transfers before the
execution, and job control tools while the job is being executed. The
job control tools are certain restricted
ways in which the institution can make
alterations to the initial allocation. Examples for such tools are
postponing a part of the job for later, or lowering the share it gets
of the CPU.