Scheduling of coupled tasks with unit processing times

Scheduling of coupled tasks with unit processing times

0.00 Avg rating0 Votes
Article ID: iaor20106376
Volume: 13
Issue: 5
Start Page Number: 453
End Page Number: 461
Publication Date: Oct 2010
Journal: Journal of Scheduling
Authors: , , , , ,
Abstract:

The coupled tasks scheduling problem was originally introduced for modeling 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 a single processor, under the assumptions that all processing times are equal to 1, the gap has exact integer length L and the precedence constraints are strict. We prove that the general problem, when L is part of the input and the precedence constraints graph is a general graph, is NP-hard in the strong sense. We also show that the special case when L=2 and the precedence constraints graph is an in-tree or an out-tree, can be solved in O(n) time.

Reviews

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