On the complexity of optimal priority assignment for periodic tasks upon identical processors

Abstract : In this paper we study global fixed-priority scheduling of periodic task systems upon identical multiprocessor platforms. Based on existing feasibility tests for periodic task systems upon identical multiprocessor platforms, we show (using a dummy priority assignment algorithm) that optimal priority assignment for these systems exists. Then we provide an algorithm based on RMUS[m/(3m-2)] that has lower complexity. Finally, we conjuncture that, contrary to the general opinion, (pseudo-) polynomial optimal priority assignment algorithms for periodic task systems upon identical processors might exist.