Queueing and Scheduling Problems with Multiple Servers

Sreoshi Banerjee and Christian Trudeau

MPRA Paper from University Library of Munich, Germany

Abstract: 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.

Keywords: waiting line; scheduling; queueing; (in)divisible jobs; multi-server; cooperative game; cost sharing (search for similar items in EconPapers)
JEL-codes: C7 C71 D3 D6 (search for similar items in EconPapers)
Date: 2026-02-14
References: Add references at CitEc
Citations:

Downloads: (external link)
https://mpra.ub.uni-muenchen.de/128053/1/MPRA_paper_128053.pdf original version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pra:mprapa:128053

Access Statistics for this paper

More papers in MPRA Paper from University Library of Munich, Germany Ludwigstraße 33, D-80539 Munich, Germany. Contact information at EDIRC.
Bibliographic data for series maintained by Joachim Winter ().