A note on scheduling identical coupled tasks in logarithmic time

The coupled tasks problem consists in scheduling image jobs on a single machine. Each job image is made of two operations with processing times image and image and a fixed required delay image between them. Operations cannot overlap in time but operations of different jobs can be interleaved. The objective is to minimize the makespan of the schedule. In this note we show that the problem with identical jobs (image) can be solved in image time when image are fixed. This problem is motivated by radar scheduling applications where tasks corresponding to transmitting radiowaves and listening to potential echoes are coupled.