This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Agnetis, A. Articles by Pacifici, A. Search for Related Content

Scheduling Problems with Two Competing Agents

Dipartimento di Ingegneria dell'Informazione, Universitaà di Siena, via Roma 56, 53100 Siena, Italy
Department of Systems and Industrial Engineering, TheUniversity of Arizona, Tucson, Arizona 85721
Dipartimento di Informatica e Automazione, Universitaà Roma Tre, Rome, Italy
Dipartimento di Informatica, Sistemi e Produzione andCentro Vito Volterra, Universitaà di Roma "Tor Vergata," Rome, Italy
agnetis{at}dii.unisi.it
pitu{at}sie.arizona.edu
pacciare{at}dia.uniroma3.it
pacifici{at}disp.uniroma2.it

We consider the scheduling problems arising when two agents, each with a set of nonpreemptive jobs, compete to perform their respective jobs on a common processing resource. Each agent wants to minimize a certain objective function, which depends on the completion times of its jobs only. The objective functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs, and total weighted completion times. We obtain different scenarios, depending on the objective function of each agent, and on the structure of the processing system (single machine or shop). For each scenario, we address the complexity of various problems, namely, finding the optimal solution for one agent with a constraint on the other agent's cost function, finding single nondominated schedules (i.e., such that a better schedule for one of the two agents necessarily results in a worse schedule for the other agent), and generating all nondominated schedules.

Subject classifications: production/scheduling: multiagent deterministic sequencing; games/group decisions: cooperative sequencing.
History: Received July 2001; revision received March 2003; accepted March 2003.