This tutorial provides an introduction into the area of polynomial time approximation
schemes. The underlying ideas, the main tools, and the standard approaches for the …

We consider a version ofmultiprocessor scheduling with the special feature that jobs may be
rejected at a certain penalty. An instance of the problem is given by m identical parallel …

We consider the problem of scheduling unrelated parallel machines subject to release dates
so as to minimize the total weighted completion time of jobs. The main contribution of this …

We present a new class of randomized approximation algorithms for unrelated parallel
machine scheduling problems with the average weighted completion time objective. The key …

We consider the problem of preemptively scheduling a set of n jobs on m (identical,
uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the …

We consider several single machine scheduling problems in which the processing time of a
job is a linear function of its starting time and jobs can be rejected by paying penalties. The …

The problem of online multiprocessor scheduling with rejection was introduced by Bartal et
al.(SIAM J. Discrete Math. 13 (1)(2000) 64–78). They show that for this problem the …

We consider the problem of minimum lateness/tardiness scheduling with rejection for which
the objective function is the sum of the maximum lateness/tardiness of the scheduled jobs …

We consider on-line scheduling of unit time jobs on a single machine with job-dependent
penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled …

In the traditional scheduling problems, it is always assumed that any job has to be
processed and the processing time is pre-given and fixed. In this paper, we address the …