Article ID: | iaor20122467 |
Volume: | 63 |
Issue: | 4 |
Start Page Number: | 524 |
End Page Number: | 529 |
Publication Date: | Apr 2012 |
Journal: | Journal of the Operational Research Society |
Authors: | Ecker K, Tana M |
Keywords: | scheduling, graphs, combinatorial optimization |
Coupled tasks scheduling was originally introduced for modelling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on one processor, under the assumptions that all processing times are equal to 1, the gap has a constant exact length and the precedence constraints are strict. Although it is proven that the problem stated above is NP‐hard in the strong sense if the precedence constraints have a form of a general graph, it is possible to solve some of its relaxed versions in polynomial time. This paper contains a solution for the problem of coupled tasks scheduling with an assumption that the precedence constraints graph has a form of chains and it presents an algorithm that can solve the problem with such assumption in time O(nlogn).