In this paper, we study schedulability analysis problems for multi-processor
real-time systems. Assume a set of real-time tasks whose execution times and
deadlines are known.  We use timed automata to describe the
non-deterministic arrival times of tasks. The schedulability problem is to
check whether the released task instances can be executed within their given
deadlines on a multi-processor platform where each processor has a task
queue to buffer task instances scheduled to run on the processor.
On the positive side, we show that the problem is decidable for systems with
non-preemptive schedulers or tasks with fixed execution times.  A surprising
negative result is that for multi-processor systems with variable task
execution times and a preemptive scheduler, the schedulability analysis
problem is undecidable, which is still an open problem in the
single-processor setting.