An optimisation approach for pre-runtime scheduling of tasks and communication in an integrated modular avionic system. (English) Zbl 1486.90087
Summary: In modern integrated modular avionic systems, applications share hardware resources on a common avionic platform. Such an architecture necessitates strict requirements on the spatial and temporal partitioning of the system to prevent fault propagation between different aircraft functions. One way to establish a temporal partitioning is through pre-runtime scheduling of the system, which involves creating a schedule for both tasks and a communication network. While avionic systems are growing more and more complex, so is the challenge of scheduling them. The scheduling of the system has an important role in the development of new avionic systems, since functionality is typically added to the system over a period of several years and a scheduling tool is used both to detect if the platform can host the new functionality and, if this is possible, to create a new schedule. For this reason an exact solution strategy for avionics scheduling is preferred over a heuristic one. In this paper we present a mathematical model for an industrially relevant avionic system and present a constraint generation procedure for the scheduling of such systems. We apply our optimisation approach to instances provided by our industrial partner. These instances are of relevance for the development of future avionic systems and contain up to 20,000 tasks to be scheduled. The computational results show that our optimisation approach can be used to create schedules for such instances within a reasonable time.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90C10 | Integer programming |
Keywords:
avionic system; scheduling; discrete optimisation; integer programming; multiprocessor scheduling; constraint generationReferences:
| [1] | Airlines Electronic Engineering Committee (AEEC) (2006) Avionics application software standard interface, ARINC specification 653 (part 1) |
| [2] | Al-Sheikh A (2011) Resource allocation in hard real-time avionic systems. Scheduling and routing problems. PhD thesis, INSA de Toulouse |
| [3] | Al-Sheikh A, Brun O, Hladik P-E, Prabhn B (2012) Strictly periodic scheduling in IMA-based architectures. Real Time Syst 48(4):359-386 · Zbl 1243.68126 · doi:10.1007/s11241-012-9148-y |
| [4] | Al-Sheikh A, Brun O, Chéramy M, Hladik P-E (2013) Optimal design of virtual links in AFDX networks. Real Time Syst 49(3):308-336 · Zbl 1317.68019 · doi:10.1007/s11241-012-9171-z |
| [5] | Balashov VV, Balakhanov VA, Kostenko VA (2014) Scheduling of computational tasks in switched network-based IMA systems. In: Proceedings of the 1st international conference on engineering and applied sciences optimization |
| [6] | Beji S, Hamadou S, Gherbi A, Mullins J (2014) SMT-based cost optimization approach for the integration of avionics functions in IMA and TTEthernet architectures. In: Proceedings of the IEEE/ACM 18th international symposium on distributed simulation and real time applications, pp 165-174 |
| [7] | Craciunas SS, Oliver RS (2014) SMT-based task- and network-level static schedule generation for time-triggered networked systems. In: Proceedings of the 22nd international conference on real-time networks and systems, pp 45-54 |
| [8] | Danielsson T, Pettersson A, Gripsborn A, Håkegård J (2016) Ethernet for avionics. Patent, 04 2016. EP 2583419 |
| [9] | Davis RI, Burns A (2011) A survey of hard real-time scheduling for multiprocessor systems. ACM Comput Surv 43(4):1-44 · Zbl 1293.68068 · doi:10.1145/1978802.1978814 |
| [10] | Easwaran A, Lee I, Sokolsky O, Vestal S (2009) A compositional scheduling framework for digital avionics systems. In: Proceedings of the 15th IEEE international conference on embedded and real-time computing systems and applications, pp 371-380 |
| [11] | Eisenbrand, Friedrich; Kesavan, Karthikeyan; Mattikalli, Raju S.; Niemeier, Martin; Nordsieck, Arnold W.; Skutella, Martin; Verschae, José; Wiese, Andreas, Solving an Avionics Real-Time Scheduling Problem by Advanced IP-Methods, 11-22 (2010), Berlin, Heidelberg · Zbl 1287.90021 · doi:10.1007/978-3-642-15775-2_2 |
| [12] | Kopetz H (2011) Real-time systems: design principles for distributed embedded applications. Real-time systems series. Springer, Berlin · Zbl 1226.68001 · doi:10.1007/978-1-4419-8237-7 |
| [13] | Lee Y-H, Kim D, Younis M, Zhou J (2000) Scheduling tool and algorithm for integrated modular avionics systems. In: Proceedings of the digital avionics systems conference, pp 1-8 |
| [14] | Leung JYT (ed) (2004) Handbook of scheduling: algorithms, models, and performance analysis. Chapman & Hall/CRC Computer and Information Science Series. Taylor & Francis, Milton Park, ISBN 9781135438852 · Zbl 1103.90002 |
| [15] | Manne AS (1960) On the job-shop scheduling problem. Oper Res 8(2):219-223 · doi:10.1287/opre.8.2.219 |
| [16] | Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J ACM 7(4):326-329 · Zbl 0100.15101 · doi:10.1145/321043.321046 |
| [17] | Pop P, Eles P, Peng Z (1999) Scheduling with optimized communication for time-triggered embedded systems. In: Proceedings of the seventh international workshop on hardware/software codesign, pp 178-182 |
| [18] | Radio Technical Commission for Aeronautics (RTCA) (2005) Integrated modular avionics (IMA) development guidance and certification considerations, RTCA DO-297 |
| [19] | Rufino, J.; Craveiro, J.; Verissimo, P.; Casimiro, A. (ed.); Lemos, R. (ed.); Gacek, C. (ed.), Architecting robustness and timeliness in a new generation of aerospace systems, No. 6420, 146-170 (2010), Berlin, Heidelberg · doi:10.1007/978-3-642-17245-8_7 |
| [20] | Tavares E, Maciel P, Sousa E, Nogueira B, Amorim L, Lira V (2012) A hierarchical pre-runtime scheduling for hard real-time systems considering fault-tolerance. In: Proceedings of the IEEE international conference on systems, man, and cybernetics, pp 1207-1212 |
| [21] | Theis J, Fohler G, Baruah S (2013) Schedule table generation for time-triggered mixed criticality systems. In: Proceedings of the workshop on mixed criticality systems at IEEE real-time systems symposium, pp 79-84 |
| [22] | Tămaş-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, pp 473-482 |
| [23] | Xu J, Parnas DL (2000) Priority scheduling versus pre-run-time scheduling. Real Time Syst 18(1):7-23 · doi:10.1023/A:1008198310125 |
| [24] | Zhang L, Goswami D, Schneider R, Chakraborty S (2014) Task- and network-level schedule co-synthesis of Ethernet-based time-triggered systems. In: Proceedings of the design automation conference (ASP-DAC), 19th Asia and South Pacific, pp 119-124 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
