nach oben

Journal of Scheduling

Erschienen in:

13.12.2018

ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors

verfasst von: Sanjoy K. Baruah, Vincenzo Bonifaci, Renato Bruni, Alberto Marchetti-Spaccamela

Erschienen in: Journal of Scheduling | Ausgabe 2/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The problem of partitioning systems of independent constrained-deadline sporadic tasks upon heterogeneous multiprocessor platforms is considered. Several different integer linear program (ILP) formulations of this problem, offering different trade-offs between effectiveness (as quantified by speedup bound) and running time efficiency, are presented. One of the formulations is leveraged to improve the best speedup guarantee known for a polynomial-time partitioning algorithm, from 12.9 to 7.83. Extensive computational results on synthetically generated instances are also provided to establish the effectiveness of the ILP formulations.

Vorheriger Artikel Correction to: Online pulse interleaving task scheduling for multifunction radar

Nächster Artikel The proactive and reactive resource-constrained project scheduling problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Although we expect that most of our results will also extend to the arbitrary-deadline sporadic task model, for ease of presentation we do not explore this issue any further in this paper, but leave it for future work.

Gurobi Optimizer. http://www.gurobi.com.

Achlioptas, D., Coja-Oghlan, A., & Ricci-Tersenghi, F. (2011). On the solution-space geometry of random constraint satisfaction problems. Random Structures & Algorithms, 38(3), 251–268.CrossRef

Albers, K., & Slomka, F. (2004). An event stream driven approximation for the analysis of real-time systems. In Proceedings of 16th Euromicro Conference on Real-Time Systems, (pp. 187–195). IEEE

Andersson, B., & Raravi, G. (2016). Scheduling constrained-deadline parallel tasks on two-type heterogeneous multiprocessors. In Proceedings of 24th International Conference on Real-Time Networks, (pp. 247–256). ACM

Baruah, S., & Bini, E. (2008). Partitioned scheduling of sporadic task systems: An ILP-based approach. In Proceedings of 2008 Conference on Design and Architectures for Signal and Image Processing

Baruah, S., Mok, A., & Rosier, L. (1990). Preemptively scheduling hard-real-time sporadic tasks on one processor. In Proceedings of 11th Real-Time Systems Symposium, (pp. 182–190). IEEE

Baruah, S. K., & Fisher, N. (2006). The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems. IEEE Transactions on Computers, 55(7), 918–923.CrossRef

Bini, E., & Buttazzo, G. C. (2005). Measuring the performance of schedulability tests. Real-Time Systems, 30(1–2), 129–154.CrossRef

Bonifaci, V., D’Angelo, G., & Marchetti-Spaccamela, A. (2017). Algorithms for hierarchical and semi-partitioned machine scheduling. In To Appear in 31st International Parallel and Distributed Processing Symposium (IPDPS 2017), IEEE.

Chen, J., & Chakraborty, S. (2013). Resource augmentation for uniprocessor and multiprocessor partitioned scheduling of sporadic real-time tasks. Real-Time Systems, 49(4), 475–516.CrossRef

Chwa, H. S., Seo, J., Lee, J., & Shin, I. (2015). Optimal real-time scheduling on two-type heterogeneous multicore platforms. In Proceedings of Real-Time Systems Symposium, IEEE

Dertouzos, M. (1974). Control robotics: The procedural control of physical processors. In Proceedings of the IFIP Congress, (pp. 807–813)

Frank, A., & Tardos, É. (1987). An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1), 49–65.CrossRef

Freuder, E. C. (1985). A sufficient condition for backtrack-bounded search. Journal of the ACM, 32(4), 755–761.CrossRef

Kamath, S. (2011). Unrelated parallel machine scheduling–perspectives and progress. OPSEARCH, 48(4), 318–334.CrossRef

Karp, R. (1972). Reducibility among combinatorial problems. In R. Miller & J. Thatcher (Eds.), Complexity of computer computations (pp. 85–103). New York: Plenum Press.CrossRef

Karp, R. M., Leighton, F. T., Rivest, R. L., Thompson, C. D., Vazirani, U. V., & Vazirani, V. V. (1987). Global wire routing in two-dimensional arrays. Algorithmica, 2, 113–129.CrossRef

Lau, L. C., Ravi, R., & Singh, M. (2011). Iterative methods in combinatorial optimization. Cambridge: Cambridge University Press.

Lenstra, J. K., Shmoys, D. B., & Tardos, É. (1990). Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46, 259–271.CrossRef

Liu, C., & Layland, J. (1973). Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1), 46–61.CrossRef

Marchetti-Spaccamela, A., Rutten, C., van der Ster, S., & Wiese, A. (2014). Assigning sporadic tasks to unrelated machines. Mathematical Programming, 152, 1–28.

Raravi, G. (2014). Real-Time Scheduling on Heterogeneous Multiprocessors. PhD thesis, Technical Institute of Porto (Portugal)

Raravi, G., Andersson, B., & Bletsas, K. (2013). Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors. Real-Time Systems, 49(1), 29–72.CrossRef

Raravi, G., Andersson, B., Nélis, V., & Bletsas, K. (2013). Task assignment algorithms for two-type heterogeneous multiprocessors. Real-Time Systems, 50(1), 87–141.CrossRef

Raravi, G., & Nélis, V. (2012). A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors. In Proceedings of 33rd Real-Time Systems Symposium, pp. 117–126. IEEE

Shmoys, D. B., & Tardos, É. (1993). An approximation algorithm for the generalized assignment problem. Mathematical Programming, 62, 461–474.CrossRef

Wiese, A., Bonifaci, V., & Baruah, S. (2013). Partitioned EDF scheduling on a few types of unrelated multiprocessors. Real-Time Systems, 49(2), 219–238.CrossRef

Titel: ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors
verfasst von: Sanjoy K. Baruah
Vincenzo Bonifaci
Renato Bruni
Alberto Marchetti-Spaccamela
Publikationsdatum: 13.12.2018
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 2/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-018-0593-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2019

Daily course pattern formulation and valid inequalities for the curriculum-based course timetabling problem

A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem

A note on minimizing total weighted completion time with an unexpected machine unavailable interval

Scheduling recurring radiotherapy appointments in an ion beam facility

The proactive and reactive resource-constrained project scheduling problem

Correction to: Online pulse interleaving task scheduling for multifunction radar