An Allocation Rule for Graph Machine Scheduling Problems

This paper studies a new type of interactive Operations Research problem, called a graph machine scheduling problem (GMS-problem). A GMS-problem combines aspects from minimum cost spanning tree problems 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 cost allocation of such an optimal order among the players involved. We restrict attention to GMS-problems on trees and propose a recursive method to solve these tree GMS-problems integrated with an allocation approach. This latter mechanism consistently and recursively uses myopic reference orders to determine potential cost savings, which will then be appropriately allocated. Interestingly, the transition process from a myopic reference order to an optimal one will be smooth using the switching of blocks of agents based on the basic notion of merge segments.