A note on scheduling identical coupled tasks in logarithmic time

AbstractThe coupled tasks problem consists in scheduling n jobs on a single machine. Each job i is made of two operations with processing times ai and bi and a fixed required delay Li 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) can be solved in O(logn) time when a,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