RT Journal Article
T1 An allocation rule for connection scheduling problems
A1 Davila Pena, Laura
A1 Borm, Peter
A1 García Jurado, Ignacio
A1 Schouten, Jop
K1 Cooperation
K1 Sequencing problems
K1 Connection scheduling problems
K1 Cost allocation
AB This paper studies so-called connection scheduling problems, a type of interactive operations research problem. A connection scheduling problem combines aspects from the minimum cost spanning tree and sequencing problems. Given a graph, we aim to first establish a connection order on the players such that the total cost of connecting them to a source is minimal and second to find a fair cost allocation of such an optimal order among the players involved. We restrict our attention to connection scheduling problems on trees and propose a recursive method to solve these tree connection scheduling problems integrated with an allocation approach. This latter mechanism consistently and recursively uses benchmark endogenous myopic orders to determine potential cost savings, which will then be appropriately allocated. Interestingly, the transition process from a benchmark myopic order to an optimal one will be smooth using the switching of blocks of agents based on the basic notion of merge segments
PB Wiley
SN 0969-6016
YR 2025
FD 2025-06-04
LK https://hdl.handle.net/10347/44476
UL https://hdl.handle.net/10347/44476
LA eng
NO Davila‐Pena, L., Borm, P., García‐Jurado, I., & Schouten, J. (2026). An allocation rule for connection scheduling problems. International Transactions in Operational Research, 33(2), 892-925.
NO Laura Davila-Pena's research was funded by the Ministry of Education, Culture and Sports of Spain (contract FPU17/02126). This work is part of the R&D projects MTM2017-87197-C3-1-P, MTM2017-87197-C3-3-P, PID2021-124030NB-C31, and PID2021-124030NB-C32, granted by MICIU/AEI/10.13039/501100011033/ and by “ERDF A way of making Europe”/EU. This research was also funded by the Xunta de Galicia (Grupos de Referencia Competitiva ED431C 2021/24 and ED431C 2020/14). The authors would like to thank the editor-in-chief, the associate editor, and the three anonymous referees for their valuable comments, which helped improve an earlier version of this paper
DS Minerva
RD 28 abr 2026