Two-agent scheduling in a two-machine open shop

作者：Liu, Peihai; Gu, Manzhan^*; Lu, Xiwen

来源：Annals of Operations Research, 2024, 333(1): 275-301.

DOI：10.1007/s10479-023-05780-x

• Scheduling
• Two-agent
• Open shop
• Approximation algorithm
• FPTAS

This paper considers several two-machine open shop problems with two agents. Each agent has an independent set of nonpreemptive jobs, and the objective is to find either a schedule minimizing a linear combination of the makespans of both agents, a schedule minimizing the makespan of one agent with the makespan of the other agent not exceeding a threshold, or all Pareto-optimal schedules with respect to the makespans of both agents. We present a number of results for the problems above, including a polynomial algorithm and a pseudo-polynomial algorithm for special cases, non-approximability, two approximation algorithms, and a fully polynomial-time approximation scheme. Finally, we run numerical experiments to show the effectiveness of the pseudo-polynomial algorithm and the approximation algorithms.

• 单位
  华东理工大学