In this paper, the problem of automatic scheduling of data exchange over a channel with centralized control in real-time avionics (RTA) systems is addressed. Examples of such channels are MIL STD-1553B multiplex data bus and Fibre Channel FC-AE-1553. Scheduling algorithms implementing greedy strategy and ant colony method are presented and evaluated experimentally. These algorithms support customization for specific requirements of the target onboard RTA system. Results of experimental evaluation demonstrate that the ant colony algorithm outperforms greedy algorithms on most of the considered classes of input data, with realistic technological requirements to data exchange. The proposed technology for data exchange scheduling is implemented in a tool system. Two case studies of industrial application of the system to the development of onboard real-time systems are described.
Aircraft internal time division command/response multiplex data bus U.S. Department of Defense, Washington, DC, 1978.
2.
Guide to digital interface standards for military avionics applications. Technical report ASSC/110/6/2-Issue 3, Avionics Systems Standardization Committee, 2006.
3.
Information Technology — Fibre Channel — Avionics Environment — Upper Layer Protocol and Profile based on MIL-STD-1553B Notice 2 (FC-AE-1553). Technical report INCITS/TR-42:2007, INCITS, 2007.
4.
LeeY.-H.KimD.YounisM.ZhouJ.Scheduling tool and algorithm for integrated modular avionics systems. In Proceedings of the 19th Digital Avionics Systems Conference, Philadelphia, Pennsylvania, USA, 2000.
5.
GoltzH.-J.PiethN.A tool for generating partition schedules of multiprocessor systems In Proceedings of the 23rd Workshop on(Constraint) Logic programming, Potsdam, Germany, 2009.
DouglassB. P.Doing hard time: developing real-time systems with UML, objects, frameworks, and patterns (Reading, Massachusetts, USA: Addison-Wesley 2004)
8.
CoffmanE. G. Eds. Computer and job-shop scheduling theory (New York: John Wiley & Sons 1976)
9.
LazarevA. A.GafarovE. R.Scheduling theory: the total tardiness problem (in Russian), 2006 (Computing Centre of the Russian Academy of Sciences, Moscow, Russia)
10.
LazarevA. A.KvaratskheliaA.TchernykhA.Solution algorithms for the total tardiness scheduling problem on a single machine. In Workshop Proceedings of the ENC04 International Conference, Colima, Mexico, 2004, pp. 474–480
11.
Della CroceF.GrossoA.PaschosV.Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problemJ. Schedul.7200485–91
12.
FedergruenA.GroeneveltH.Preemptive scheduling of uniform machines by ordinary network flow techniqueManage. Sci.3231986341–349
13.
TanaevV. S.GordonV. S.ShafranskyY. M.Scheduling theory, single-stage systems (Dordrecht, The Netherlands: Kluwer 1994)
14.
GusD. S.FurugyanM. G.Scheduling computations and memory load for single-processor hard real-time systems (in Russian)Model. Control Process. (2004): 162–169
15.
GusD. S.FurugyanM. G.Computation scheduling in multiprocessor real-time automatic control systems with constrained processor memoryAutom. Rem. Control6622005295–303
16.
KostenkoV. A.Scheduling algorithms for single-device real-time systems (in Russian) In Proceedings of the 3rd Conference onMethods and tools for information processing, Moscow, Russia, 2009, pp. 245–258
17.
KostenkoV. A.GuryanovE. S.An algorithm for scheduling exchanges over a bus with centralized control and an analysis of its efficiencyProgr. Comp. Softw.3162005340–346
18.
DorigoM.Optimization, learning and natural algorithms PhD Thesis, Politechnico di Milano, Milano, 1992.
19.
ShtovbaS. D.Ant algorithms: Theory and applicationsProgr. Comp. Softw.3142005167–178
20.
BalashovV. V.KostenkoV. A.SmelianskyR. L.A tool system for automatic scheduling of data exchange in real-time distributed avionics systems In Proceedings of the 2nd EUCASS European Conference onAerospace sciences, Brussels, Belgium, 2007.
21.
BakhmurovA. G.BalashovV. V.ChistolinovM. V.SmelianskyR. L.VolkanovD. Y.YoushchenkoN. V.A hardware-in-the-loop simulation environment for integration of distributed avionics systems In Proceedings of the 3rd EUCASS European Conference onAerospace sciences, Versailles, France, 2009.
22.
LiuC. L.LaylandJ. W.Scheduling algorithms for multiprogramming in a hard-real-time environmentJ. ACM201197346–61
23.
BychkovI. A.KostenkoV. A.Problems of data exchange scheduling and network topology selection for arbitrated loop (in Russian) In Proceedings of the 3rd Conference onMethods and tools for information processing, Moscow, Russia, 2009, pp. 204–214
24.
BalashovV. V.Recommendation generation algorithms for scheduling of data exchange through a channel with centralized controlJ. Comp. Syst. Sci. Int.4662007887–894
25.
BalashovV. V.ShestovP. E.Recommendation generation for providing compatibility of requirements to data exchange over a bus with centralized control in real-time embedded systems (in Russian)In Proceedings of the 4th International Conference onParallel computations and control problems, Moscow, Russia, 2008, pp. 1385–1404
