Two-agent scheduling on a single machine with release dates

摘要

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.