Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap

Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap

0.00 Avg rating0 Votes
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: ,
Keywords: scheduling, graphs, combinatorial optimization
Abstract:

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).

Reviews

Required fields are marked *. Your email address will not be published.