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.