A note on scheduling identical coupled tasks in logarithmic time

The coupled tasks problem consists in scheduling n jobs on a single machine. Each job i is made of two operations with Processing times a(i) and b(i) and a fixed required delay L-i 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 (for all i, a(i) = a, b(i) = b, L-i = L) call be solved in O(log n) 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. (C) 2009 Elsevier B.V. All rights reserved.