Approximating Coupled-Task Scheduling Problems with Equal Exact Delays

We consider a coupled-task single machine scheduling problem with equal exact delays and makespan as the objective function. We design a 3-approximation algorithm for the general case of this problem. We also prove that the existence of a \((1.25-\varepsilon )\)-approximation algorithm implies P = NP. The inapproximability result remains valid for the case when the processing times of the two operations of each job are equal. We prove that this case is approximable within a factor of 1.5.