A note on scheduling identical coupled tasks in logarithmic time

The coupled tasks problem consists in scheduling nn jobs on a single machine. Each job ii is made of two operations with processing times aiai and bibi and a fixed required delay LiLi 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 (∀i,ai=a,bi=b,Li=L∀i,ai=a,bi=b,Li=L) can be solved in O(logn)O(logn) time when a,b,La,b,L are fixed. This problem is motivated by radar scheduling applications where tasks corresponding to transmitting radiowaves and listening to potential echoes are coupled.