User: Guest  Login
Title:

Approximability of Scheduling with Fixed Jobs

Document type:
Technical Report
Author(s):
M. Scharbrodt; A. Steger; H. Weisser
Abstract:
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...     »
Keywords:
polynomial approximation scheme; scheduling; makespan
Year:
1999
Year / month:
1999-03-01 00:00:00
Pages:
23
 BibTeX