{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:58:47Z","timestamp":1771037927863,"version":"3.50.1"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T00:00:00Z","timestamp":1537833600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s11241-018-9320-0","type":"journal-article","created":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T02:48:53Z","timestamp":1537843733000},"page":"209-247","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Efficient offline scheduling of task-sets with complex constraints on large distributed time-triggered systems"],"prefix":"10.1007","volume":"55","author":[{"given":"Ali","family":"Syed","sequence":"first","affiliation":[]},{"given":"Gerhard","family":"Fohler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,25]]},"reference":[{"issue":"11","key":"9320_CR1","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1109\/71.809575","volume":"10","author":"TF Abdelzaher","year":"1999","unstructured":"Abdelzaher TF, Shin KG (1999) Combined task and message scheduling in distributed real-time systems. IEEE Trans Parallel Distrib Syst 10(11):1179\u20131191","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"1","key":"9320_CR2","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1109\/12.822566","volume":"49","author":"TF Abdelzaher","year":"2000","unstructured":"Abdelzaher TF, Shin KG (2000) Period-based load partitioning and assignment for large real-time applications. IEEE Trans Comput 49(1):81\u201387","journal-title":"IEEE Trans Comput"},{"key":"9320_CR3","doi-asserted-by":"crossref","unstructured":"Ahmad I, Kwok YK (1998) Optimal and near-optimal allocation of precedence-constrained tasks to parallel processors: defying the high complexity using effective search techniques. In: International conference on parallel processing, IEEE, pp 424\u2013431","DOI":"10.1109\/ICPP.1998.708514"},{"key":"9320_CR4","unstructured":"Anwikar V, Bhaduri P (2010) Timing analysis of real-time embedded systems using model checking. In: 18th international conference on real-time and network systems, pp 119\u2013128"},{"key":"9320_CR5","unstructured":"AS6802 (2011) Time-triggered ethernet. Standard AS6802, Society of Automotive Engineers International"},{"issue":"4","key":"9320_CR6","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01995675","volume":"2","author":"SK Baruah","year":"1990","unstructured":"Baruah SK, Rosier LE, Howell RR (1990) Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Syst 2(4):301\u2013324","journal-title":"Real-Time Syst"},{"issue":"1","key":"9320_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/nav.3800220113","volume":"22","author":"P Bratley","year":"1975","unstructured":"Bratley P, Florian M, Robillard P (1975) Scheduling with earliest start and due date constraints on multiple machines. Naval Res Logist Q 22(1):165\u2013173","journal-title":"Naval Res Logist Q"},{"issue":"3","key":"9320_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF00365326","volume":"2","author":"H Chetto","year":"1990","unstructured":"Chetto H, Silly M, Bouchentouf T (1990) Dynamic scheduling of real-time tasks under precedence constraints. Real-Time Syst 2(3):181\u2013194","journal-title":"Real-Time Syst"},{"key":"9320_CR9","unstructured":"Coelho RF (2017) Blah. Ph.D. thesis, Technische Universit\u00e4t Kaiserslautern"},{"key":"9320_CR10","volume-title":"Introduction to algorithms","author":"T Cormen","year":"2001","unstructured":"Cormen T, Leiserson C, Rivest R, Stein C (2001) Introduction to algorithms. MIT Press, Cambridge"},{"issue":"2","key":"9320_CR11","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s11241-015-9244-x","volume":"52","author":"SS Craciunas","year":"2016","unstructured":"Craciunas SS, Oliver RS (2016) Combined task- and network-level scheduling for distributed time-triggered systems. Real-Time Syst 52(2):161\u2013200. \n                    https:\/\/doi.org\/10.1007\/s11241-015-9244-x","journal-title":"Real-Time Syst"},{"key":"9320_CR12","doi-asserted-by":"crossref","unstructured":"Dick RP, Rhodes DL, Wolf W (1998) TGFF: task graphs for free. In: Proceedings of the 6th international workshop on hardware\/software codesign, CODES\/CASHE\u201998. IEEE Computer Society, Washington, DC, pp 97\u2013101. \n                    http:\/\/dl.acm.org\/citation.cfm?id=278241.278309","DOI":"10.1145\/278241.278309"},{"key":"9320_CR13","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1007\/3-540-45578-7_53","volume-title":"Principles and practice of constraint programming","author":"C Ekelin","year":"2001","unstructured":"Ekelin C, Jonsson J (2001) Evaluation of search heuristics for embedded system scheduling problems. In: Walsh T (ed) Principles and practice of constraint programming, vol 2239. Lecture notes in computer science. Springer, Berlin, pp 640\u2013654"},{"key":"9320_CR14","unstructured":"Fohler G (1994) Flexibility in statically scheduled real-time systems. PhD thesis, TNF, Wien, \u00d6sterreich"},{"key":"9320_CR15","doi-asserted-by":"crossref","unstructured":"Glover F, Kochenberger G (2003) Handbook of metaheuristics. International series in operations research & management science. Springer, Berlin. \n                    https:\/\/books.google.de\/books?id=O_10T_KeqOgC","DOI":"10.1007\/b101874"},{"key":"9320_CR16","doi-asserted-by":"crossref","unstructured":"Goossens J, Devillers R (1999) Feasibility intervals for the deadline driven scheduler with arbitrary deadlines. In: Proceedings of the sixth international conference on real-time computing systems and applications, RTCSA\u201999. IEEE Computer Society, Washington, DC. \n                    http:\/\/dl.acm.org\/citation.cfm?id=519167.828794","DOI":"10.1109\/RTCSA.1999.811193"},{"key":"9320_CR17","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.jss.2016.05.040","volume":"119","author":"A Guasque","year":"2016","unstructured":"Guasque A, Balbastre P, Crespo A (2016) Real-time hierarchical systems with arbitrary scheduling at global level. J Syst Softw 119:70\u201386. \n                    https:\/\/doi.org\/10.1016\/j.jss.2016.05.040","journal-title":"J Syst Softw"},{"issue":"3","key":"9320_CR18","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1109\/TII.2010.2052819","volume":"6","author":"Z Hanzalek","year":"2010","unstructured":"Hanzalek Z, Burget P, Sucha P (2010) Profinet IO IRT message scheduling with temporal constraints. IEEE Trans Ind Inf 6(3):369\u2013380. \n                    https:\/\/doi.org\/10.1109\/TII.2010.2052819","journal-title":"IEEE Trans Ind Inf"},{"issue":"2","key":"9320_CR19","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P Hart","year":"1968","unstructured":"Hart P, Nilsson N, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100\u2013107","journal-title":"IEEE Trans Syst Sci Cybern"},{"key":"9320_CR20","unstructured":"H\u00f6nig U, Schiffmann W (2004) Fast optimal task graph scheduling by means of an optimized parallel A*-algorithm. In: PDPTA, pp 842\u2013848"},{"key":"9320_CR21","unstructured":"Itier JB (2007) A380 integrated modular avionics. In: Proceedings of the ARTIST2 meeting on integrated modular avionics, vol\u00a01, pp 72\u201375"},{"key":"9320_CR22","doi-asserted-by":"crossref","unstructured":"Jeffay K, Stanat D, Martel C (1991) On non-preemptive scheduling of periodic and sporadic tasks. In: Twelfth proceedings of real-time systems symposium, pp 129\u2013139","DOI":"10.1109\/REAL.1991.160366"},{"key":"9320_CR23","doi-asserted-by":"crossref","unstructured":"Jonsson J (1999) Effective complexity reduction for optimal scheduling of distributed real-time applications. In: Proceedings of the IEEE international conference on distributed computing systems, pp 360\u2013369","DOI":"10.1109\/ICDCS.1999.776538"},{"key":"9320_CR24","doi-asserted-by":"publisher","unstructured":"Kopetz H (1992) Sparse time versus dense time in distributed real-time systems. In: Proceedings of the 12th international conference on distributed computing systems, 1992, pp 460\u2013467, \n                    https:\/\/doi.org\/10.1109\/ICDCS.1992.235008","DOI":"10.1109\/ICDCS.1992.235008"},{"issue":"1","key":"9320_CR25","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0004-3702(85)90084-0","volume":"27","author":"RE Korf","year":"1985","unstructured":"Korf RE (1985) Depth-first iterative-deepening: an optimal admissible tree search. Artif Intell 27(1):97\u2013109","journal-title":"Artif Intell"},{"issue":"3","key":"9320_CR26","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s10462-009-9140-7","volume":"29","author":"S Kurkovsky","year":"2009","unstructured":"Kurkovsky S (2009) Experimenting with IDA* search algorithm in heterogeneous pervasive environments. Artif Intell Rev 29(3):277\u2013286. \n                    https:\/\/doi.org\/10.1007\/s10462-009-9140-7","journal-title":"Artif Intell Rev"},{"issue":"3","key":"9320_CR27","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"AH Land","year":"1960","unstructured":"Land AH, Doig AG (1960) An automatic method for solving discrete programming problems. Econometrica 28(3):497\u2013520","journal-title":"Econometrica"},{"issue":"3","key":"9320_CR28","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0020-0190(80)90123-4","volume":"11","author":"JYT Leung","year":"1980","unstructured":"Leung JYT, Merrill M (1980) A note on preemptive scheduling of periodic, real-time tasks. Inf Process Lett 11(3):115\u2013118","journal-title":"Inf Process Lett"},{"key":"9320_CR29","unstructured":"Marouf M, Sorel Y (2010) Schedulability conditions for non-preemptive hard real-time tasks with strict period. In: Marouf M, Sorel Y (eds) Proceedings of 18th international conference on real-time and network systems, RTNS\u201910, Toulouse, France. \n                    https:\/\/hal.inria.fr\/inria-00566359"},{"key":"9320_CR30","doi-asserted-by":"crossref","unstructured":"Marouf M, Sorel Y (2011) Scheduling non-preemptive hard real-time tasks with strict periods. In: 2011 IEEE 16th conference on emerging technologies & factory automation (ETFA), pp 1\u20138","DOI":"10.1109\/ETFA.2011.6059014"},{"key":"9320_CR31","unstructured":"McKinsey (2013) The internet of things and the future of manufacturing. \n                    http:\/\/www.mckinsey.com\/business-functions\/digital-mckinsey\/our-insights\/the-internet-of-things-and-the-future-of-manufacturing\n                    \n                  . Accessed 10 Nov 2016"},{"key":"9320_CR32","unstructured":"Peng DT, Shin K (1989) Static allocation of periodic tasks with precedence constraints in distributed real-time systems. In: 9th international conference on distributed computing systems, pp 190\u2013198"},{"issue":"3","key":"9320_CR33","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1109\/32.221134","volume":"19","author":"DT Peng","year":"1993","unstructured":"Peng DT, Shin K (1993) Optimal scheduling of cooperative tasks in a distributed system using an enumerative method. IEEE Trans Softw Eng 19(3):253\u2013267","journal-title":"IEEE Trans Softw Eng"},{"key":"9320_CR34","doi-asserted-by":"crossref","unstructured":"Pozo F, Steiner W, Rodriguez-Navas G, Hansson H (2015) A decomposition approach for SMT-based schedule synthesis for time-triggered networks. In: 2015 IEEE 20th conference on emerging technologies & factory automation (ETFA), pp 1\u20138","DOI":"10.1109\/ETFA.2015.7301436"},{"key":"9320_CR35","doi-asserted-by":"crossref","unstructured":"Pozo F, Rodriguez-Navas G, Steiner W, Hansson H (2016) Period-aware segmented synthesis of schedules for multi-hop time-triggered networks. In: 2016 IEEE 22nd international conference on embedded and real-time computing systems and applications (RTCSA), pp 170\u2013175","DOI":"10.1109\/RTCSA.2016.42"},{"key":"9320_CR36","unstructured":"Pozo F, Rodriguez-Navas G, Hansson H, Steiner W (2017) Schedule synthesis for next generation time-triggered networks. Ph.D. thesis, M\u00e4lardalen Real-Time Research Centre, M\u00e4lardalen University. \n                    http:\/\/www.es.mdh.se\/publications\/4698-"},{"issue":"5","key":"9320_CR37","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1007\/s11241-015-9232-1","volume":"51","author":"W Puffitsch","year":"2015","unstructured":"Puffitsch W, Noulard E, Pagetti C (2015) Off-line mapping of multi-rate dependent task sets to many-core platforms. Real-Time Syst 51(5):526\u2013565. \n                    https:\/\/doi.org\/10.1007\/s11241-015-9232-1","journal-title":"Real-Time Syst"},{"key":"9320_CR38","unstructured":"Rao VN, Kumar V, Ramesh K (1987) A parallel implementation of iterative-deepening-A*. In: Proceedings of the sixth national conference on artificial intelligence, vol 1, pp 178\u2013182"},{"key":"9320_CR39","doi-asserted-by":"crossref","unstructured":"Ronngren S, Shirazi B (1995) Static multiprocessor scheduling of periodic real-time tasks with precedence constraints and communication costs. In: Proceedings of the twenty-eighth Hawaii international conference on system sciences, vol\u00a02, pp 143\u2013152","DOI":"10.1109\/HICSS.1995.375468"},{"key":"9320_CR40","unstructured":"Schorr S (2015) Adaptive real-time scheduling and resource management on multicore architectures. Ph.D. thesis, Technische Universit\u00e4t Kaiserslautern"},{"issue":"2","key":"9320_CR41","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1145\/356689.356692","volume":"9","author":"R Sedgewick","year":"1977","unstructured":"Sedgewick R (1977) Permutation generation methods. ACM Comput Surv 9(2):137\u2013164","journal-title":"ACM Comput Surv"},{"key":"9320_CR42","doi-asserted-by":"crossref","unstructured":"Steiner W (2010) An evaluation of SMT-based schedule synthesis for time-triggered multi-hop networks. In: Real-time systems symposium (RTSS), IEEE, pp 375\u2013384","DOI":"10.1109\/RTSS.2010.25"},{"key":"9320_CR43","unstructured":"Syed AAJ, Fohler G (2014) Search-tree exploration for scheduling using PIDA*. Technical report, August 2014"},{"key":"9320_CR44","doi-asserted-by":"crossref","unstructured":"Tamas-Selicean D, Pop P, Steiner W (2012) Synthesis of communication schedules for TTEthernet-based mixed-criticality systems. In: Proceedings of the eighth IEEE\/ACM\/IFIP international conference on hardware\/software codesign and system synthesis. ACM, New York, pp 473\u2013482","DOI":"10.1145\/2380445.2380518"},{"key":"9320_CR45","unstructured":"Theis J, Fohler G, Baruah S (2013) Schedule table generation for time-triggered mixed criticality systems. In: 1st workshop on mixed criticality systems, IEEE real-time systems symposium"},{"issue":"2","key":"9320_CR46","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF00365407","volume":"4","author":"K Tindell","year":"1992","unstructured":"Tindell K, Burns A, Wellings A (1992) Allocating hard real time tasks: an NP-hard problem made easy. Real-Time Syst 4(2):145\u2013165","journal-title":"Real-Time Syst"},{"key":"9320_CR47","volume-title":"Applied combinatorics","author":"A Tucker","year":"2006","unstructured":"Tucker A (2006) Applied combinatorics. Wiley, New York"},{"key":"9320_CR48","unstructured":"Waez MTB, Dingel J, Rudie K (2011) Timed automata for the development of real-time systems. Research Report 2011-579, Queen\u2019s University-School of Computing"},{"issue":"4","key":"9320_CR49","doi-asserted-by":"publisher","first-page":"2233","DOI":"10.1109\/TII.2014.2300753","volume":"10","author":"LD Xu","year":"2014","unstructured":"Xu LD, He W, Li S (2014) Internet of things in industries: a survey. IEEE Trans Ind Inf 10(4):2233\u20132243. \n                    https:\/\/doi.org\/10.1109\/TII.2014.2300753","journal-title":"IEEE Trans Ind Inf"},{"key":"9320_CR50","doi-asserted-by":"crossref","unstructured":"Zhang L, Goswami D, Schneider R, Chakraborty S (2014) Task- and network-level schedule co-synthesis of ethernet-based time-triggered systems. In: 19th Asia and South Pacific design automation conference (ASP-DAC), pp 119\u2013124","DOI":"10.1109\/ASPDAC.2014.6742876"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-018-9320-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11241-018-9320-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-018-9320-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T03:38:05Z","timestamp":1569382685000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11241-018-9320-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,25]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["9320"],"URL":"https:\/\/doi.org\/10.1007\/s11241-018-9320-0","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,25]]},"assertion":[{"value":"25 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}