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.
Citation
Title changed on 16-06-2014