Queueing and Scheduling Problems with Multiple Servers

Banerjee, Sreoshi and Trudeau, Christian (2026): Queueing and Scheduling Problems with Multiple Servers.

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.

• Item Type: MPRA Paper
• Language: English
• Keywords: waiting line, scheduling, queueing, (in)divisible jobs, multi-server, cooperative game, cost sharing
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; D - Microeconomics > D3 - Distribution; D - Microeconomics > D6 - Welfare Economics

References

A. Atay and C. Trudeau. Queueing games with an endogenous number of machines. Games and Economic Behavior, 144:104–125, 2024.

A. Atay and C. Trudeau. Optimistic and pessimistic approaches for cooperative games. European Journal of Operational Research, 326:725–733, 2026.

S. Banerjee and M. Mitra. Lorenz optimality for sequencing problems with welfare bounds. Economics Letters, 205:109963, 2021.

S. Banerjee, P. De, and M. Mitra. Generalized welfare lower bounds and strategyproofness in sequencing problems. Social Choice and Welfare, 63(2):323–357, 2024.

L. Bao, C. Q. Wu, X. Bu, N. Ren, and M. Shen. Performance modeling and workflow scheduling of microservice-based applications in clouds. IEEE Transactions on Parallel and Distributed Systems, 30:2114–2129, 2019.

P. Calleja, P. Borm, H. Hamers, F. Klijn, and M. Slikker. On a new class of parallel sequencing situations and related games. Annals of Operations Research, 109(1): 265–277, 2002.

Y. Chun. No-envy in queueing problems. Economic Theory, 29:151–162, 2006a.

Y. Chun. A pessimistic approach to the queueing problem. Mathematical Social Sciences, 51(2):171–181, 2006b.

Y. Chun and E. J. Heo. Queueing problems with two parallel servers. International Journal of Economic Theory, 4(2):299–315, 2008.

Y. Chun and T. Hokari. On the coincidence of the Shapley value and the nucleolus in queueing problems. Seoul Journal of Economics, 20(2):223–238, 2007.

Y. Chun and M. Mitra. Subgroup additivity in the queueing problem. European Journal of Operational Research, 238(1):281–289, 2014.

Y. Chun, M. Mitra, and S. Mutuswami. Egalitarian equivalence and strategyproofness in the queueing problem. Economic Theory, 56:425–442, 2014.

Y. Chun, M. Mitra, and S. Mutuswami. A characterization of the symmetrically balanced VCG rule in the queueing problem. Games and Economic Behavior, 118: 486–490, 2019.

P. De and M. Mitra. Incentives and justice for sequencing problems. Economic Theory, 64:239–264, 2017.

P. De and M. Mitra. Balanced implementability of sequencing rules. Games and Economic Behavior, 118:342–353, 2019.

M. Grabisch. k-order additive discrete fuzzy measures and their representation. Fuzzy Sets and Systems, 92(2):167–189, 1997.

H. Hamers, F. Klijn, and J. Suijs. On the balancedness of multiple machine sequencing games. European Journal of Operational Research, 119(3):678–691, 1999.

C¸ . Kayı and E. Ramaekers. Characterizations of Pareto-efficient, fair, and strategyproof allocation rules in queueing problems. Games and Economic Behavior, 68(1): 220–232, 2010.

Y.-D. Kim, S.-O. Shim, S.-B. Kim, Y.-C. Choi, and H. M. Yoon. Parallel machine scheduling considering a job-splitting property. International Journal of Production Research, 42(21):4531–4546, 2004.

L. Kleinrock. Communication nets; stochastic message flow and delay. Dover Publications, Inc., USA, 1972.

J.-H. Lee, H. Jang, and H.-J. Kim. Iterative job splitting algorithms for parallel machine scheduling with job splitting and setup resource constraints. Journal of the Operational Research Society, 72(4):780–799, 2021.

F. Maniquet. A characterization of the Shapley value in queueing problems. Journal of Economic Theory, 109(1):90–103, 2003.

M. Mitra. Incomplete information and multiple machine queueing problems. European Journal of Operational Research, 165(1):251–266, 2005.

M. Mitra and S. Mutuswami. No-envy in the queueing problem with multiple identical machines. Game Theory and Networks: New Perspectives and Directions, pages 161– 176, 2021.

H. Moulin. On scheduling fees to prevent merging, splitting, and transferring of jobs. Mathematics of Operations Research, 32(2):266–283, 2007.

H. Moulin. Proportional scheduling, split-proofness, and merge-proofness. Games and Economic Behavior, 63(2):567–587, 2008.

T. G. Robertazzi. Ten reasons to use divisible load theory. Computer, 36(5):63–68, 2003.

W. E. Smith et al. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3(1-2):59–66, 1956.

W.-L. Wang, H.-Y. Wang, Y.-W. Zhao, L.-P. Zhang, and X.-L. Xu. Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm. Computers & Operations Research, 40(5):1196–1206, 2013.