Polynomial time optimal algorithms for time slot assignment ofvariable bandwidth systems

Considers the optimal (i.e., minimum length) time slot assignment problem for variable bandwidth switching systems. Existing algorithms for this problem are known to be pseudo-polynomial. The practical question of finding a fast optimal algorithm, as well as the theoretical question of whether the above problem is NP-complete were left open. The authors present a technique to show polynomial time complexity of some time slot assignment algorithms. Such a technique applies to an algorithm proposed by Chalasani and Varma in 1991 (called the CV algorithm), as well as to a network flow based optimal algorithm, proposed in the present paper for the first time. The CV algorithm and the one proposed are slightly different. Thus, the authors give an answer to both the above questions, by establishing that the problem is in P, and by showing effective algorithms for it     

Complexity of minimum length scheduling for precedence constrained messages in distributed systems

Switching networks are the core of many communication and multiprocessor systems. In these systems, a set of entities (communication equipment or processors) communicate through the switching network by exchanging messages. Simultaneous transmission or reception of two 01 more different messages through an input or output port results in the corruption of the messages (also called collision), which are useless and must be retransmitted later. This causes a performance degradation. Collisions can be avoided only by a proper scheduling of the messages. The same problem also arises in single-hop purely optical WDM systems, where simultaneous reception or transmission over the same wavelength channel results in a collision. In this paper, we study the problem of minimum length scheduling of a set of messages subject to precedence constraints. We show that the decision version of the problem is NP-complete even in very restricted cases. This means that the optimization problem cannot be solved in polynomial time, unless P=NP. Since the problem cannot be optimally solved by fast algorithms, we then investigate the existence of polynomial time approximation algorithms, by first proving that approximation algorithms cannot exist with performance ratio bounded by 4/3 or smaller and successively presenting an /spl epsiv/-approximation algorithm with /spl epsiv/<2 for the case of two precedence classes of messages. Finally, we assess the existence of an asymptotically optimal schedule in the general case of an unrestricted number of precedence classes.