| Article ID: | iaor20123974 |
| Volume: | 63 |
| Issue: | 4 |
| Start Page Number: | 763 |
| End Page Number: | 780 |
| Publication Date: | Aug 2012 |
| Journal: | Algorithmica |
| Authors: | Bonifaci Vincenzo, Marchetti-Spaccamela Alberto |
| Keywords: | computational analysis: parallel computers |
We give the first algorithm for testing the feasibility of a system of sporadic real‐time tasks on a set of identical processors, solving an open problem in the area of multiprocessor real‐time scheduling (Baruah and Pruhs, 2009). We also investigate the related notion of schedulability and a notion that we call online feasibility. Finally, we show that discrete‐time schedules are as powerful as continuous‐time schedules, which answers another open question in the above mentioned survey.