Narrow Results

Papadimitrjou and Yannakakis showed that unit execution time tasks in interval orders can be scheduled in linear time on N processors when communication cost is ignored. The objective function was to minimize the schedule length. They have also shown that the generalization of this problem to arbitrary execution times is NP-complete. In this paper, we study the problem of scheduling task graphs with communication on N processors when the task graph is an interval order. We prove that this scheduling problem can be solved in polynomial time when the execution cost of the system tasks is identical and equal to the communication cost between any pair of processors. We introduce an algorithm of O(Ne) to minimize the schedule length, where e is the number of arcs in the interval order.

In the framework of the representability of ordinal qualitative data by means of interval-valued correspondences, we study interval orders defined on a nonempty set X. We analyse the continuous case, that corresponds to a set endowed with a topology that furnishes an idea of continuity, so that it becomes natural to ask for the existence of quantifications based on interval-valued mappings from the set of data into the real numbers under preservation of order and topology. In the present paper we solve a continuous representability problem for interval orders. We furnish a characterization of the representability of an interval order through a pair of continuous real-valued functions so that each element in X has associated in a continuous manner a characteristic interval or equivalently a symmetric triangular fuzzy number.

Given a binary relation defined on a set, we study its representability by means of a monotonic function that takes values on a suitable universal codomain (that depends on the kind of relation considered). We pay an special attention to the representability of interval orders, studying their alternative universal codomains, some of them equivalent to the set of symmetric triangular fuzzy numbers.