טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAgmon Ben-Yehuda Orna
SubjectIncentives and General Welfare Functions in the Off-line
Scheduling Problem
DepartmentDepartment of Applied Mathematics
Supervisor Professor Rann Smorodinsky


Abstract

Several agents wish to execute jobs 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 in order to act optimally, the institute must know the true lengths - an information it does not posses.


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 implementation of job control tools during the execution. A job control tool is a certain algorithm for altering 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.