Two agent scheduling with a central selection mechanism

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 shortest 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 worst-case performance of classical priority rules compared to an optimal strategy. Finally, we consider minimax strategies, i.e. algorithms optimizing the objective of one agent in the worst case.