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 an element of {1, 2}. Finally, if m greater than or equal to 3, balancedness is established for two special classes of In-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. (C) 1999 Elsevier science B.V. All rights reserved.