An approximation algorithm for identical parallel machine scheduling with resource dependent processing times

摘要

We present a (3.5 + epsilon)-approximation algorithm for a scheduling problem on identical parallel machines with the objective to mimimize the makespan. The processing times depend on the usage of a single renewable resource where at any point of time at most k units from the resource are available. (C) 2007 Elsevier B.V. All rights reserved.