文献类型：期刊文献

英文题名：Two-agent single-machine scheduling with release dates to minimize the makespan

作者：Yu, Jin[1];Liu, Peihai[1];Lu, Xiwen[1]

机构：[1]East China Univ Sci & Technol, Sch Sci, Shanghai 200237, Peoples R China

年份：2023

卷号：17

期号：8

起止页码：1915

外文期刊名：OPTIMIZATION LETTERS

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

基金：AcknowledgementsThis work is supported by the National Nature Science Foundation of China(11871213). The authors would like to thank anonymous referees whose comments helped a lot to improve this paper.

语种：英文

外文关键词：Two-agent scheduling; Makespan; Release date; Approximation algorithm; FPTAS

摘要：We consider two-agent scheduling on a single-machine with release dates. There are two agents, namely, A and B. Each agent has his own job set. Each job has a release date and a processing time. All jobs need to be scheduled on a single machine. The objective function of each agent is the makespan with respect to his jobs, i.e., the maximum completion time. We consider two problems, namely the problem to minimize the makespans of agent A with the makespan of agent B not greater than a positive number Q given in advance, and the problem to minimize the weighted sum of both agents' makespans. For the first problem, we drive an approximation algorithm with a worst-case ratio of 3/2 . Furthermore, we show that this problem admits a fully polynomial-time approximation scheme(FPTAS). For the second problem, we propose an improved approximation algorithm with a worst-case ratio of 1 + theta/ (1+theta)(2), where theta > 0 is the weight of agent B.