Queueing and Scheduling Problems with Multiple Servers

We examine the implications of extending the queueing and scheduling problems from the single-server to the multiple-server cases. In particular, we discuss three assumptions on job divisibility: jobs can be assumed to be indivisible (must be processed continuously on a single server), discretely divisible (a job can be divided in a series of unit-length tasks that can be processed simultaneously on multiple servers) or continuously divisible (a job can be divided in intervals as small as desired). We examine if the corresponding optimistic and pessimistic cost functions (in which we assume that a group is served first and last, respectively) satisfy the properties of convexity/concavity and 2-additivity. Our results show that with multiple servers, while all properties hold under continuous divisibility, they largely fail otherwise. In particular, 2-additivity does not carry over, and pessimistic functions are no longer concave. Optimistic functions retain the convexity property in most cases. These negative results indicate that multi-server problems require fundamentally new analytical approaches, as single-server techniques do not generalize. We also establish that the anticore of the optimistic function is always a non-empty subset of the core of the pessimistic function, providing bounds even when classical properties fail.