Approximability of Scheduling with Fixed Jobs

The scheduling problem of minimizing the makespan is among the most well studied problems --- especially in the field of approximation. In modern industrial software however, it has become standard to work on a variant of this problem, where some of the jobs are already fixed in the schedule. The remaining jobs are to be assigned to the machines in such a way that they do not overlap with fixed jobs. In this paper we first focus on simple algorithms for this problem which have a reasonable performance guarantee and are easy to implement in practical settings. This is followed by a polynomial time approximation scheme (PTAS) for the case that the number m of machines is constant. Moreover, we show that, unless P = NP, there is no arbitrarily close approximation in the general case when the number of machines is part of the input. This will be extended by showing that there is no asymptotic PTAS in the general machine case. We finally show that there exists no FPTAS in the constant machine case, unless P = NP.     «

The scheduling problem of minimizing the makespan is among the most well studied problems --- especially in the field of approximation. In modern industrial software however, it has become standard to work on a variant of this problem, where some of the jobs are already fixed in the schedule. The remaining jobs are to be assigned to the machines in such a way that they do not overlap with fixed jobs. In this paper we first focus on simple algorithms for this problem which have a reasonable perfo...     »