文献类型：期刊文献

英文题名：Two-agent scheduling on a single machine with release dates

作者：Liu, Peihai[1];Gu, Manzhan[2];Li, Ganggang[3]

机构：[1]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China;[2]Shanghai Univ Finance & Econ, Sch Math, Shanghai 200433, Peoples R China;[3]Jiangxi Univ Finance & Econ, Sch Math, Nanchang 330077, Jiangxi, Peoples R China

年份：2019

卷号：111

起止页码：35

外文期刊名：COMPUTERS & OPERATIONS RESEARCH

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

基金：This work is supported by the National Nature Science Foundation of China (11371137, 11871213) and Jiangxi Provincial Department of Education Science and Technology Project (GJJ150447).

语种：英文

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

摘要：This paper considers a two-agent scheduling problem, in which all jobs belong to two agents A and B, and each job has a release date. The objective is to schedule all jobs non-preemptively on a single machine such that the linear combination of the makespans of the two agents, i.e., C-max(A) + theta C-max(B) (theta >= 1), is minimized. It is known that the problem is NP-hard in the ordinary sense. For this case, we provide an approximation algorithm with worst-case ratio 1 + theta/1+theta+theta(2). We also propose a Fully Polynomial Time Approximation Scheme (FPTAS) for the problem under study. Finally, computational experiments are conducted to verify the effectiveness of the approximation algorithm and the FPTAS. (C) 2019 Elsevier Ltd. All rights reserved.