Minimising the makespan in a two-machine open shop scheduling with competing agents
研究双机开放车间中两个竞争代理的调度问题，在限制代理B最大完工时间的前提下最小化代理A的完工时间，提出了精确算法和启发式方法，实验表明算法可处理多达5000个作业。
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.