文献类型：期刊文献

英文题名：Optimal algorithms for preemptive two-agent scheduling on uniform parallel machines

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

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

年份：2024

卷号：1012

外文期刊名：THEORETICAL COMPUTER SCIENCE

收录：;EI(收录号：20242916716549);WOS:【SCI-EXPANDED(收录号:WOS:001272590300001)】；

基金：The authors thank the referees for reviewing the paper. This work is supported by the National Nature Science Foundation of China (12371317) .

语种：英文

外文关键词：Two-agent scheduling; Uniform machines; Job preemption; Makespan minimization; Total completion time minimization

摘要：This paper studies two scheduling problems involving two agents A and B, where each agent has an independent set of jobs and all jobs are to be processed preemptively on uniform parallel machines. The aims of the two problems are to minimize the objective function value of agent A with the makespan of agent B not exceeding a threshold T. In the first problem, there are m machines and the objective function of agent A is the makespan. In the second problem, there are two machines and the objective function of agent A is the total completion time. For each of the two problems, we propose an optimal algorithm and obtain some extended results.