Scheduling real-time computations with separation constraints

Given a graph and a positive integer k, the Separation Problem is to find a linear layout for the vertices such that each pair of adjacent vertices has a distance of at least k in the layout. A polynomial time algorithm has been studied earlier for the special case when the graph is a directed forest. In this paper, we study the problem when the roots of the trees in the forest have different constraints on their earliest starting positions. We present an O(n log n) algorithm for the problem with n vertices in the forest. We then use the algorithm to schedule real-time jobs with minimum distance constraints.