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

Switching networks are the core of many communication and multiprocessor sy stems. In these systems, a set of entities (communication equipment or proc essors) communicate through the switching network by exchanging messages. S imultaneous transmission or reception or two or more different messages thr ough an input or output port results in the corruption of the messages (als o called collision), which are useless and must be retransmitted later. Thi s causes a performance degradation. Collisions can be avoided only by a pro per scheduling of the messages. The same problem also arises in single-hop purely optical WDM systems, where simultaneous reception or transmission ov er the same wavelength channel results in a collision. In this paper, we st udy the problem of minimum length scheduling of a set of messages subject t o precedence constraints We show that the decision version of the problem i s NP-complete even in very restricted cases. This means that the optimizati on problem cannot be solved in polynomial time, unless P=NP. Since the prob lem cannot be optimally solved by fast algorithms, we then investigate the existence of polynomial time approximation algorithms, by first proving tha t approximation algorithms cannot exist with performance ratio bounded by 4 /3 or smaller and successively presenting an epsilon -approximation algorit hm with epsilon < 2 for the case of two precedence classes of messages. Fin ally, we assess the existence of an asymptotically optimal schedule in the general case of an unrestricted number of precedence classes.