Minimising the makespan in a two-machine open shop scheduling with competing agents

We study a two-machine open shop with two competing agents, where each agent owns a disjoint set of jobs processed on shared machines. We address a constrained objective motivated by service-level agreements: minimise the makespan of agent A subject to an upper bound Q on the makespan of agent B. We first refine the computational complexity landscape of this constrained model under several structured processing-time settings, delineating polynomially solvable cases and establishing hardness results for restricted variants. To compute optimal solutions, we introduce three mixed-integer programming formulations suited for small instances and develop an exact branch-and-bound algorithm for larger instances that integrates problem-specific branching rules, strong lower bounds, and a fast constructive heuristic for upper bounds. Computational experiments on randomly generated instances demonstrate that the branch-and-bound approach scales to instances with up to 5000 jobs within short runtimes in the tested settings, while the heuristic consistently produces high-quality schedules with small optimality gaps.