On the balancedness of multiple machine sequencing games

摘要

This paper takes a game theoretical approach to sequencing situations with m parallel and identical machines. We show that in a cooperative environment cooperative m-sequencing games, which involve n players, give rise to m-machine games, which involve m players. Here, n corresponds to the number of jobs in an m-sequencing situation, and m corresponds to the number of machines in the same m-sequencing situation. We prove that an m-sequencing game is balanced if and only if the corresponding m-machine game is balanced. Furthermore, it is shown that m-sequencing games are balanced if m is a member of the set {1,2}. Finally, if m greater than or equal 3, balancedness is established for two special classes of m-sequencing games. Furthermore, we consider a special class of m-sequencing situations in a noncooperative setting and show that a transfer payments scheme exists that is both incentive compatible and budget balanced.