We introduce the problem of Flexible Scheduling on Related Machines with Assignment Restrictions (FSRM). In this problem the input consists of a set of machines and a set of jobs. Each machine has a finite capacity, and each job has a resource requirement interval, a profit per allocated unit of resource, and a set of machines that can potentially supply the requirement. A feasible solution is an allocation of machine resources to jobs such that: (i) a machine resource can be allocated to a job only if it is a potential supplier of this job, (ii) the amount of machine resources allocated by a machine is bounded by its capacity, and (iii) the amount of resources that are allocated to a job is either in its requirement interval or zero. Notice that a job can be serviced by multiple machines. The goal is to find a feasible allocation that maximizes the overall profit. We focus on r-FSRM in which the required resource of a job is at most an r-fraction of (or r times) the capacity of each potential machine. FSRM is motivated by resource allocation problems arising in cellular networks and in cloud computing. Specifically, FSRM models the problem of assigning clients to base stations in 4G cellular networks. We present a 2-approximation algorithm for 1-FSRM and a 1/(1-r)-approximation algorithm for r-FSRM, for any r ∈ (0,1). Both are based on the local ratio technique and on maximum flow computations. We also present an LP-rounding 2-approximation algorithm for a flexible version of the Generalized Assignment Problem that also applies to 1-FSRM. Finally, we give an Ω(r/(log r)) lower bound on the approximation ratio for r-FSRM (assuming P ≠ NP).
展开▼
