Multiserver Scheduling with Contiguity Constraints

We consider a scheduling problem in which multiple servers are available to service multiple users in a time-slotted system. Each server has a time-dependent and user-dependent service rate for each user at each timeslot. A schedule specifies which server serves which user per timeslot, with a typical objective of maximizing the total rate that the users receive. The servers are numbered by a set of consecutive integers. A strict contiguity constraint enforces that each user is served by at most one contiguous interval of the servers. We show that a strict contiguity requirement makes the scheduling problem APX hard to solve, which means we cannot approximate an optimal schedule arbitrarily closely. On the positive side, we also offer two approximation algorithms, a simple one that guarantees a logarithmic approximation and a more complex one that guarantees a constant approximation. In addition, we also present a complete taxonomy of the scheduling variants that consider issues in the following dimensions. (i) Strict contiguity vs; soft contiguity, where the latter allows multiple intervals of servers to serve the same user but imposes a penalty; (ii) Full buffer vs finite buffer, where the former assumes each user always has a large queue and for the latter the service a user receives is upper bounded by its queue size; (iii) slot-by-slot scheduling vs template scheduling, where the former creates a schedule for every timeslot and the latter creates a schedule for multiple timeslots at a time; (iv) Time-variant vs time-invariant service rates for template scheduling. For each variant, we present optimal algorithms if possible and approximation algorithms whenever NP-hardness prevails.