文献类型：期刊文献

英文题名：Two-agent scheduling in a two-machine open shop

作者：Liu, Peihai[1];Gu, Manzhan[2];Lu, Xiwen[1]

机构：[1]East China Univ Sci & Technol, Sch Math, Shanghai, Peoples R China;[2]Shanghai Univ Finance & Econ, Sch Math, Shanghai 200433, Peoples R China

年份：2024

卷号：333

期号：1

起止页码：275

外文期刊名：ANNALS OF OPERATIONS RESEARCH

收录：;WOS:【SCI-EXPANDED(收录号:WOS:001127004100001)】；

基金：This work is supported by the National Nature Science Foundation of China (11871213).

语种：英文

外文关键词：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.