Single Machine Scheduling of Coupled Task with Resource Consumption

We investigate coupled task scheduling problems under constrained resource availability on a single machine, which are of fundamental interest and already NP-hard even in this basic setting. In this model, every job Formula: see text comprises two tasks. Their processing times are distinct, and they are separated by a fixed time interval. For the second task, the job-specific processing time depends on the amount of resource allocated to it. The aim is to minimize the makespan or the total completion time, under the resource constraints. For the goal of minimizing the makespan, we develop a Formula: see text-approximation algorithm for the general case. Then we propose a 3-approximation algorithm for the special case where the time intervals are all equal. For the goal of minimizing the total completion time, we propose a 3-approximation algorithm when all time intervals are equal. Finally, we propose a 2-approximation algorithm when the processing time of the first task is equal to the time interval.