Acceptance Testing; Mission-Critical Systems; Satellite Systems; Test Case Scheduling; Multi-Objective Optimization
Abstract :
[en] Mission-critical system, such as satellite systems, healthcare systems, and nuclear power plant control systems, undergo rigorous testing to ensure they meet specific operational requirements throughout their operation. This includes Operational Acceptance Testing (OAT), which aims to ensure that the system functions correctly under real-world operational conditions. In satellite development, In-Orbit Testing (IOT) is a crucial OAT activity performed regularly and as needed after deployment in orbit to check the satellite's performance and ensure that operational requirements are met. The scheduling of an IOT campaign, which executes multiple IOT procedures, is an important yet challenging problem, as it accounts for various factors, including satellite visibility, antenna usage costs, testing time periods, and operational constraints. To address the IOT scheduling problem, we propose a multi-objective approach to generate near-optimal IOT schedules, accounting for operational costs, fragmentation (i.e., the splitting of tests), and resource efficiency, which align with practitioners' objectives for IOT scheduling. Our industrial case study with SES Techcom shows significant improvements, as follows: an average improvement of 49.4% in the cost objective, 60.4% in the fragmentation objective, and 30% in the resource usage objective, compared to our baselines. Additionally, our approach improves cost efficiency by 538% and resource usage efficiency by 39.42% compared to manually constructed schedules provided by practitioners, while requiring only 12.5% of the time needed for manual IOT scheduling.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > SVV - Software Verification and Validation
Disciplines :
Computer science
Author, co-author :
Ollando, Raphaël
SHIN, Seung Yeob ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > SVV
Minardi, Mario; SES Techcom
Sidiropoulos, Nikolas; SES Techcom
External co-authors :
no
Language :
English
Title :
Test Schedule Generation for Acceptance Testing of Mission-Critical Satellite Systems
Publication date :
2025
Journal title :
Empirical Software Engineering
ISSN :
1382-3256
eISSN :
1573-7616
Publisher :
Springer Nature, Germany
Peer reviewed :
Peer Reviewed verified by ORBi
FnR Project :
FNR14016225 - INSTRUCT - Integrated Satellite-terrestrial Systems For Ubiquitous Beyond 5g Communications, 2020 (01/10/2020-30/09/2026) - Symeon Chatzinotas
Name of the research project :
R-AGR-3929 - IPBG19/14016225/INSTRUCT - SES - CHATZINOTAS Symeon
This version of the article has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10664-025-10737-8. Use of this Accepted Version is subject to the publisher's Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms.
S. Ali P. Arcaini D. Pradhan S.A. Safdar T. Yue Quality indicators in search-based software engineering: an empirical evaluation ACM Trans Softw Eng Methodol (TOSEM) 29 2 1 29 10.1145/3375636
Ammann P, Offutt J (2016) Introduction to software testing, 2nd edn. Cambridge University Press
A. Arcuri L. Briand A hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering Softw Testing Verification Reliab 24 3 219 250 10.1002/stvr.1486
Arcuri A, Fraser G (2011) On parameter tuning in search based software engineering. In: Proceedings of the 3rd International Symposium on Search Based Software Engineering (SSBSE’11). pp 33–47
Arrieta A, Wang S, Sagardui G, Etxeberria L (2016) Test case prioritization of configurable cyber-physical systems with weight-based search algorithms. In: Proceedings of the genetic and evolutionary computation conference 2016. Association for Computing Machinery, New York, NY, USA, pp 1053–1060
A. Arrieta S. Wang U. Markiegi A. Arruabarrena L. Etxeberria G. Sagardui Pareto efficient multi-objective black-box test case selection for simulation-based testing Inf Softw Technol 114 137 154 10.1016/j.infsof.2019.06.009
A. Arrieta S. Wang G. Sagardui L. Etxeberria Search-based test case prioritization for simulation-based testing of cyber-physical system product lines J Syst Softw 149 1 34 10.1016/j.jss.2018.09.055
Balanis CA (2016) Antenna theory: analysis and design. John Wiley & Sons
J.E. Bell P.R. McMullen Ant colony optimization techniques for the vehicle routing problem Adv Eng Inform 18 1 41 48 10.1016/j.aei.2004.07.001
J. Blank K. Deb Y. Dhebar S. Bandaru H. Seada Generating well-spaced points on a unit simplex for evolutionary many-objective optimization IEEE Trans Evol Comput 25 1 48 60 10.1109/TEVC.2020.2992387
Busjaeger B, Xie T (2016) Learning for test prioritization: an industrial case study. In: 24th ACM SIGSOFT International symposium on foundations of software engineering. pp 975–980
C. Catal D. Mishra Test case prioritization: a systematic mapping study Software Qual J 21 445 478 10.1007/s11219-012-9181-z
Coello CAC (2000) Treating constraints as objectives for single-objective evolutionary optimization. Eng Optimization+ A35 32(3):275–308
F.D. Davis V. Venkatesh Toward preprototype user acceptance testing of new information systems: implications for software project management IEEE Trans Eng Manage 51 1 31 46 10.1109/TEM.2003.822468
Deb K, Agrawal S (1999) A niched-penalty approach for constraint handling in genetic algorithms. In: Artificial neural nets and genetic algorithms: proceedings of the international conference in Portorož. pp 235–243
K. Deb H. Jain An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints IEEE Trans Evol Comput 18 4 577 601 10.1109/TEVC.2013.2281535
K. Deb A. Pratap S. Agarwal T. Meyarivan A fast and elitist multiobjective genetic algorithm: NSGA-II IEEE Trans Evol Comput 6 2 182 197 10.1109/4235.996017
Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern Part B (Cybernetics) 26(1):29–41
Finsterwalder M (2001) Automating acceptance tests for GUI applications in an extreme programming environment. In: 2nd international conference on extreme programming and flexible processes in software engineering (XP’01). pp 114–117
Fortescue P, Stark J, Swinerd G (2011) Spacecraft systems engineering. John Wiley & Sons, Ltd
Gao K, Wu G, Zhu J (2013) Multi-satellite observation scheduling based on a hybrid ant colony optimization. In: Proceedings of the 2nd International Symposium on Computer, Communication, Control and Automation (ISCCCA 2013). pp 675–678
M. Gen R. Cheng Genetic algorithms and engineering optimization USA John Wiley & Sons 10.1002/9780470172261 7
M. Harman S.A. Mansouri Y. Zhang Search-based software engineering: trends, techniques and applications ACM Comput Surv (CSUR) 45 1 1 61 10.1145/2379776.2379787
A. Homaifar C.X. Qi S.H. Lai Constrained optimization via genetic algorithms Simulation 62 4 242 253 10.1177/003754979406200405
M. Khatibsyarbini M.A. Isa D.N. Jawawi R. Tumeng Test case prioritization approaches in regression testing: a systematic literature review Inf Softw Technol 93 74 93 10.1016/j.infsof.2017.08.014
M. Kong P. Tian Y. Kao A new ant colony optimization algorithm for the multidimensional knapsack problem Comput Oper Res 35 8 2672 2683 2586391 10.1016/j.cor.2006.12.029
H.K. Leung P.W. Wong A study of user acceptance tests Software Qual J 6 137 149 10.1023/A:1018503800709
Z. Li M. Harman R.M. Hierons Search algorithms for regression test case prioritization IEEE Trans Software Eng 33 4 225 237 10.1109/TSE.2007.38
Liebel G, Alégroth E, Feldt R (2013) State-of-practice in GUI-based system and acceptance testing: An industrial multiple-case study. In: Euromicro 39th conference on software engineering and advanced applications. IEEE, pp 17–24
Liskin O, Herrmann C, Knauss E, Kurpick T, Rumpe B, Schneider K (2012) Supporting acceptance testing in distributed software projects with integrated feedback systems: experiences and requirements. In: IEEE 7th international conference on global software engineering. IEEE, pp 84–93
Löffler R, Güldali B, Geisen S (2010) Towards model-based acceptance testing for scrum. Softwaretechnik-Trends Band 30, Heft 3
Luke S (2013) Essentials of metaheuristics, 2nd edn. Lulu, available for free at http://cs.gmu.edu/~sean/book/metaheuristics/
H.B. Mann D.R. Whitney On a test of whether one of two random variables is stochastically larger than the other Ann Math Stat 18 1 50 60 22058 10.1214/aoms/1177730491
Maral G, Bousquet M, Sun Z (2020) Satellite communications systems: systems, techniques and technology. John Wiley & Sons
F. Marinelli S. Nocella F. Rossi S. Smriglio A Lagrangian heuristic for satellite range scheduling with resource constraints Comput Oper Res 38 11 1572 1583 2781551 10.1016/j.cor.2011.01.016
Mkaouer MW, Kessentini M, Bechikh S, Deb K, Ó Cinnéide M (2014) High dimensional search-based software engineering: finding tradeoffs among 15 objectives for automating software refactoring using NSGA-III. In: Proceedings of the 2014 annual conference on genetic and evolutionary computation. Association for Computing Machinery, New York, NY, USA, pp 1263–1270
R. Montemanni L.M. Gambardella A.E. Rizzoli A.V. Donati Ant colony system for a dynamic vehicle routing problem J Comb Optim 10 4 327 343 2191795 10.1007/s10878-005-4922-6
O’Connor P, Kleyner A (2012) Practical reliability engineering. John Wiley & Sons
Ollando R, Shin SY, Minardi M, Sidiropoulos N (2025) [artifact repository] test schedule generation for acceptance testing of mission-critical satellite systems. https://figshare.com/s/58931c1953bd4f9a0136
H.P. Schwefel Numerical optimization of computer models USA John Wiley & Sons
Shin SY, Nejati S, Sabetzadeh M, Briand LC, Zimmer F (2018) Test case prioritization for acceptance testing of cyber physical systems: a multi-objective search-based approach. In: Proceedings of the 27th ACM SIGSOFT international symposium on software testing and analysis (ISSTA’18). pp 49–60
T. Stützle H.H. Hoos Max-min ant system Futur Gener Comput Syst 16 8 889 914 10.1016/S0167-739X(00)00043-1
Van Veldhuizen DA, Lamont GB (1998) Multiobjective evolutionary algorithm research: A history and analysis. Tech. Rep. TR-98-03, Air Force Institute of Technology
Vargha A, Delaney HD (2000) A critique and improvement of the “cl” common language effect size statistics of McGraw and Wong. J Educ Behav Stat 25(2):101–132
Wang S, Ali S, Yue T, Bakkeli Ø, Liaaen M (2016a) Enhancing test case prioritization in an industrial setting with resource awareness and multi-objective search. In: 38th IEEE/ACM international conference on software engineering companion. pp 182–191
Wang S, Ali S, Yue T, Li Y, Liaaen M (2016b) A practical guide to select quality indicators for assessing pareto-based search algorithms in search-based software engineering. In: Proceedings of the 38th international conference on software engineering, ICSE ’16. pp 631–642
West DB (2001) Introduction to graph theory, 2nd edn. Pearson College Div
G. Wu J. Liu M. Ma D. Qiu A two-phase scheduling method with the consideration of task clustering for earth observing satellites Comput Oper Res 40 7 1884 1894 10.1016/j.cor.2013.02.009
N. Zhang F. Zr K. Lj Guidance-solution based ant colony optimization for satellite control resource scheduling problem Appl Intell 35 3 436 444 10.1007/s10489-010-0234-3
Q. Zhang H. Li MOEA/D: a multiobjective evolutionary algorithm based on decomposition IEEE Trans Evol Comput 11 6 712 731 10.1109/TEVC.2007.892759
Z. Zhang N. Zhang Z. Feng Multi-satellite control resource scheduling based on ant colony optimization Expert Syst Appl 41 6 2816 2823 10.1016/j.eswa.2013.10.014
Z. Zhang F. Hu N. Zhang Ant colony algorithm for satellite control resource scheduling problem Appl Intell 48 10 3295 3305 10.1007/s10489-018-1144-z
Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms — a comparative case study. In: Proceedings of the 5th international conference on parallel problem solving from nature, PPSN ’V. pp 292–301
Zitzler E, Laumanns M, Thiele L (2001) SPEA2: Improving the strength pareto evolutionary algorithm. TIK report 103
