Optimization Online


Scheduling the Tasks of Two Agents with a Central Selection Mechanism

Gaia Nicosia (nicosia***at***dia.uniroma3.it)
Andrea Pacifici (pacifici***at***disp.uniroma2.it)
Ulrich Pferschy (pferschy***at***uni-graz.at)

Abstract: We address a class of deterministic scheduling problems in which two agents compete for the usage of a single machine. The agents have their own objective functions and submit in each round an arbitrary, unprocessed task from their buffer for possible selection. In each round the smaller of the two submitted tasks is chosen and processed on the machine. We consider the problems under two distinct perspectives: First, we look at them from a centralized point of view as bicriteria optimization problems and try to characterize the set of Pareto optimal solutions. Then, the problems are viewed under the perspective of a single agent. In particular, we measure the performance of simple priority rules suggesting to an agent how to sequence its own tasks in order to optimize its own objective function. Then we consider minimax strategies, i.e. algorithms optimizing the objective of one agent in the worst case.

Keywords: scheduling, multi-agent optimization, bicriteria optimization

Category 1: Combinatorial Optimization

Category 2: Applications -- OR and Management Sciences (Scheduling )

Category 3: Other Topics (Game Theory )

Citation: Title changed on 16-06-2014

Download: [PDF]

Entry Submitted: 01/24/2014
Entry Accepted: 02/01/2014
Entry Last Modified: 06/16/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society