## Competitive two-agent scheduling and its applications.(English)Zbl 1233.90163

Summary: We consider a scheduling environment with $$m$$ ($$m\geqslant 1$$) identical machines in parallel and two agents. Agent A is responsible for $$n_{1}$$ jobs and has a given objective function with regard to these jobs; agent B is responsible for $$n_{2}$$ jobs and has an objective function that may be either the same or different from the one of agent A. The problem is to find a schedule for the $$n_{1} + n_{2}$$ jobs that minimizes the objective of agent A (with regard to his $$n_{1}$$ jobs) while keeping the objective of agent B (with regard to his $$n_{2}$$ jobs) below or at a fixed level Q. The special case with a single machine has recently been considered in the literature, and a variety of results have been obtained for two-agent models with objectives such as $$f_{max}, \sum w_{j}C_{j}$$, and $$\sum U_{j}$$. In this paper, we generalize these results and solve one of the problems that had remained open. Furthermore, we enlarge the framework for the two-agent scheduling problem by including the total tardiness objective, allowing for preemptions, and considering jobs with different release dates; we consider also identical machines in parallel. We furthermore establish the relationships between two-agent scheduling problems and other areas within the scheduling field, namely rescheduling and scheduling subject to availability constraints.

### MSC:

 90B35 Deterministic scheduling theory in operations research
Full Text: