  We present a unified framework for designing deterministic monotone
polynomial time approximation schemes (PTAS's) for a wide class of scheduling
problems on uniformly related machines. This class includes (among others)
minimizing the makespan, maximizing the minimum load, and minimizing the l_p
norm of the machine loads vector. Previously, this kind of result was only
known for the makespan objective. Monotone algorithms have the property that an
increase in the speed of a machine cannot decrease the amount of work assigned
to it. The key idea of our novel method is to show that for goal functions that
are sufficiently well-behaved functions of the machine loads, it is possible to
compute in polynomial time a highly structured nearly optimal schedule.
Monotone approximation schemes have an important role in the emerging area of
algorithmic mechanism design. In the game-theoretical setting of these
scheduling problems there is a social goal, which is one of the objective
functions that we study. Each machine is controlled by a selfish
single-parameter agent, where its private information is its cost of processing
a unit sized job, which is also the inverse of the speed of its machine. Each
agent wishes to maximize its own profit, defined as the payment it receives
from the mechanism minus its cost for processing all jobs assigned to it, and
places a bid which corresponds to its private information. For each one of the
problems, we show that we can calculate payments that guarantee truthfulness in
an efficient manner. Thus, there exists a dominant strategy where agents report
their true speeds, and we show the existence of a truthful mechanism which can
be implemented in polynomial time, where the social goal is approximated within
a factor of 1+epsilon for every epsilon>0.
