Approximation Algorithms for Scheduling with Reservations

We study the problem of non-preemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations. This setting is practically relevant because for various reasons, some machines may not be available during specified time intervals. The objective is to minimize the makespan Cmax, which is the maximum completion time. The general case of the problem is inapproximable unless P = NP; hence we study a suitable strongly NP-hard restriction, namely the case where at least one machine is always available. For this setting we contribute approximation schemes, complemeted by inapproximability results. The approach is based on algorithms for multiple subset sum problems; our technique yields a PTAS which is best possible in the sense that an FPTAS is ruled out unless P = NP. The PTAS presented here is the rst one for the problem under consideration; so far, not even for well-know special cases approximation schemes have been proposed. Furthermore we derive a low cost algorithm with a vonstant approximation ratio and discuss FPTAes for special cases as well as the complexity of the problem if m is part of the input.

Logo BII

BII

Cite

Citation style:
Could not load citation form.

Rights

Use and reproduction:No Creative Commons license - The provisions of the German Copyright Act (UrhG) apply.Please note that individual components of the publication may be subject to other licensing or copyright conditions.