Authors: Florian Diedrich Klaus Jansen Fanny Pascual Denis Trystram
Publish Date: 2009/01/21
Volume: 58, Issue: 2, Pages: 391-404
Abstract
We study the problem of nonpreemptively scheduling n independent sequential jobs on a system of m identical parallel machines in the presence of reservations where m is constant 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 C max which is the maximum completion timeThe general case of the problem is inapproximable unless mathsf P=mathsf NP hence we study a suitable strongly mathsf NP hard restriction namely the case where at least one machine is always available For this setting we contribute approximation schemes complemented 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 mathsf P=mathsf NP The PTAS presented here is the first one for the problem under consideration so far not even for wellknown special cases approximation schemes have been proposed Furthermore we derive a low cost algorithm with a constant approximation ratio and discuss FPTASes for special cases as well as the complexity of the problem if m is part of the inputF Diedrich’s research was supported in part by a grant “DAAD Doktorandenstipendium” of the German Academic Exchange Service and in part by EU research project AEOLUS Algorithmic Principles for Building Efficient Overlay Computers EU contract number 015964 Part of this work done while visiting the LIG Grenoble University Supported in part by DFG priority program 1126 “Algorithmics of Large and Complex Networks” furthermore supported in part by a PPP funding “Scheduling in Communication Networks” D/05/06936 granted by the DAAD
Keywords: