Atlas: On a new class of parallel sequencing situations and related games by Pedro Calleja

Atlas home || Conferences | Abstracts | about Atlas

First World Congress of the Game Theory Society (Games 2000)
July 24-28, 2000
Basque Country University and Fundacion B.B.V.
Bilbao, Spain

Organizers
Ehud Kalai, Federico Valenciano

View Abstracts
Conference Homepage

On a new class of parallel sequencing situations and related games
by
Pedro Calleja
Depart. of Economical, Financial and Actuarial Mathematics, University of Barcelona
Coauthors: Peter Borm, Herbert Hamers and Flip Klijn (Department of Econometrics and CentER, Tilburg University)

Abstract: Sequencing or scheduling situations consist of a number of jobs (tasks, operations) that have to be processed on a number of machines. The processing time of a job on a specific machine is the time this machine takes to handle this job. Sequencing situations can be classified by the number of machines, the specific properties of the machines (e.g. parallel, identical), the chosen restrictions on the jobs (e.g. ready times, due dates, flow constraints), and the chosen cost criterion (e.g. weighted completion time, makespan).

By assuming that there exists an initial schedule before the machines start processing, one can establish a relation between cooperative games and sequencing situations in the following way. Under the assumption that each job is owned by one agent, a group of agents (a coalition) can save costs by rearranging their jobs in a way that is admissible with respect to this initial schedule. By defining the value of a coalition as the maximal cost savings a coalition can make in this way, we obtain a cooperative sequencing game related to a sequencing situation. The above game-theoretic approach was initiated by Curiel, Pederzoli, Tijs (1989) and is used to analyse several classes of sequencing situations.

This paper considers sequencing situations with m parallel machines in which no restrictions on the jobs are imposed. Contrary to other papers in this field, it is assumed that each agent owns m jobs. More precisely, we assume that each agent has precisely one job in front of each machine. The costs of an agent depend linearly on the completion time of all his jobs.

First, we describe a rearrangement procedure that provides an optimal processing order of the jobs of the agents for some particular situations. Secondly, we introduce a class of cooperative games that arises from these sequencing situations. Finally, these games are investigated with respect to the properties of balancedness and convexity.

Keywords: cooperative game theory, scheduling

Date received: June 20, 2000