Online scheduling for a Testing-as-a-Service system

• Autorzy: Rudy J. , Smutnicki C.

Identyfikatory

DOI

10.24425/bpasts.2020.134187

• Języki publikacji: EN

Abstrakty

EN

The problem of performing software tests using Testing-as-a-Service cloud environment is considered and formulated as an~online cluster scheduling on parallel machines with total flowtime criterion. A mathematical model is proposed. Several properties of the problem, including solution feasibility and connection to the classic scheduling on parallel machines are discussed. A family of algorithms based on a new priority rule called the Smallest Remaining Load (SRL) is proposed. We prove that algorithms from that family are not competitive relative to each other. Computer experiment using real-life data indicated that the SRL algorithm using the longest job sub-strategy is the best in performance. This algorithm is then compared with the Simulated Annealing metaheuristic. Results indicate that the metaheuristic rarely outperforms the SRL algorithm, obtaining worse results most of the time, which is counter-intuitive for a metaheuristic. Finally, we test the accuracy of prediction of processing times of jobs. The results indicate high (91.4%) accuracy for predicting processing times of test cases and even higher (98.7%) for prediction of remaining load of test suites. Results also show that schedules obtained through prediction are stable (coefficient of variation is 0.2–3.7%) and do not affect most of the algorithms (around 1% difference in flowtime), proving the considered problem is semi-clairvoyant. For the Largest Remaining Load rule, the predicted values tend to perform better than the actual values. The use of predicted values affects the SRL algorithm the most (up to 15% flowtime increase), but it still outperforms other algorithms.

Słowa kluczowe

EN

discrete optimization; online scheduling; cloud computing; Testing-as-a-Service

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2020
• Tom: Vol. 68, nr 4
• Strony: 869--882
• Opis fizyczny: Bibliogr. 29 poz., rys., tab.

Twórcy

autor

Rudy J.

• Wrocław University of Science and Technology, Department of Computer Engineering, Wybrzeże Wyspiańskiego 27, 50-370, Wrocław, Poland

autor

Smutnicki C.

• Wrocław University of Science and Technology, Department of Computer Engineering, Wybrzeże Wyspiańskiego 27, 50-370, Wrocław, Poland

Bibliografia

• [1] D. Kumar and K. Mishra, “The impacts of test automation on software’s cost, quality and time to market”, Procedia Comput. Sci. 79, 8–15 (2016).
• [2] J. Musial, M. Guzek, P. Bouvry, and J. Blazewicz, “A note on the complexity of scheduling of communicationaware directed acyclic graph”, textitBull. Pol. Ac.: Tech. 66 (2), 187–191 (2018).
• [3] L. Yu, L. Zhang, H. Xiang, Y. Su, W. Zhao, and J. Zhu, “A framework of testing as a service”, in 2009 International Conference on Management and Service Science, 2009, pp. 1–4.
• [4] L. Yu, W. Tsai, X. Chen, L. Liu, Y. Zhao, L. Tang, and W. Zhao, “Testing as a service over cloud”, in 2010 Fifth IEEE International Symposium on Service Oriented System Engineering, 2010, pp. 181–188.
• [5] A. Sathe and D.R. Kulkarni, “Study of testing as a service (taas)–cost effective framework for taas in cloud environment”, International Journal of Application or Innovation in Engineering and Management (IJAIEM) 2 (5), 239–243, (2013).
• [6] P. Lampe and J. Rudy, “Models and scheduling algorithms for a software testing system over cloud”, in Contemporary Complex Systems and Their Dependability, pp. 326–337, Eds. W. Zamojski, J. Mazurkiewicz, J. Sugier, T. Walkowiak, and J. Kacprzyk, Cham: Springer International Publishing, 2019.
• [7] S.-J. Lee, Y.-C. Lin, K.-H. Lin, and J.-L. You, “A system for composing and delivering heterogeneous web testing software as a composite web testing service”, J. Inf. Sci. Eng. 34 (3), 631–648 (2018).
• [8] J. Gao, X. Bai, and W. Tsai, “Cloud testing issues, challenges, needs and practice”, Software Engineering: An International Journal 1(1), 9–23 (2011). [Online]. Available: http://www.seij.dce.edu/Paper%5Cn1.pdf
• [9] R. V. Binder, “Optimal scheduling for combinatorial software testing and design of experiments”, in 2018 IEEE International Conference on Software Testing, Verification and Validation Workshops, 2018, pp. 295–301.
• [10] J. Rudy, “Online multi-criteria scheduling for testing as a service cloud platform”, in Smart Innovations in Engineering and Technology, pp. 34–52, Eds. R. Klempous and J. Nikodem, Cham: Springer International Publishing, 2020.
• [11] S. Tahvili, “Multi-criteria optimization of system integration testing”, Ph.D. dissertation, RISE SICS Västerås, 2018.
• [12] P. Lampe, “Fuzzy job scheduling for testing as a service platform”, in Smart Innovations in Engineering and Technology, pp. 25–33, Eds. R. Klempous and J. Nikodem, Cham: Springer International Publishing, 2020.
• [13] A. Ali, H.A. Maghawry, and N. Badr, “Automated parallel gui testing as a service for mobile applications”, J. Software: Evol. Process 30 (10), e1963 (2018), [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/smr.1963
• [14] I. Gog, M. Schwarzkopf, A. Gleave, R.N.M. Watson, and S. Hand, “Firmament: Fast, Centralized Cluster Scheduling at Scale”, in Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation, 2016, pp. 99–115.
• [15] J. Rasley, K. Karanasos, S. Kandula, R. Fonseca, M. Vojnovic, and S. Rao, “Efficient queue management for cluster scheduling”, in Proceedings of the Eleventh European Conference on Computer Systems, ser. EuroSys ’16, New York, USA, 2016, pp. 36:1–36:15.
• [16] P. Delgado, F. Dinu, A.-M. Kermarrec, and W. Zwaenepoel, “Hawk: Hybrid datacenter scheduling”, in Proceedings of the 2015 USENIX Conference on Usenix Annual Technical Conferece, Berkeley: USENIX Association, 2015, pp. 499–510. [Online]. Available: http://dl.acm.org/citation.cfm?id=2813767.2813804.
• [17] K. Lee, J.Y.-T. Leung, and M.L. Pinedo, “Makespan minimization in online scheduling with machine eligibility”, Ann. Oper. Res. 204(1), 189–222 (2013).
• [18] P. Delgado, D. Didona, F. Dinu, and W. Zwaenepoel, “Job-aware scheduling in eagle: Divide and stick to your probes”, in Proceedings of the Seventh ACM Symposium on Cloud Computing, ser. SoCC ’16. New York, USA, 2016, pp. 497–509. [Online]. Available: http://doi.acm.org/10.1145/2987550.2987563
• [19] C. Reiss, A. Tumanov, G.R. Ganger, R.H. Katz, and M.A. Kozuch, “Heterogeneity and dynamicity of clouds at scale: Google trace analysis”, in Proceedings of the Third ACM Symposium on Cloud Computing, ser. SoCC ’12, New York, USA, 2012, pp. 7:1–7:13.
• [20] S. Leonardi and D. Raz, “Approximating total flow time on parallel machines”, J. Comput. Syst. Sci. Int. 73 (6), 875–891 (2007).
• [21] G. Dósa, A. Fügenschuh, Z. Tan, Z. Tuza, and K. W ̨ esek, “Tight lower bounds for semi-online scheduling on two uniform machines with known optimum”, Cent. Eur. J. Oper. Res. 27(4), 1107–1130 (2019).
• [22] G. Iordache, M. Boboila, F. Pop, C. Stratan, and V. Cristea, “Decentralized grid scheduling using genetic algorithms”, in Metaheuristics for Scheduling in Distributed Computing Environments, Eds. F. Xhafa and A. Abraham, Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 215–246.
• [23] F. Xhafa, E. Alba, and B. Dorronsoro, “Efficient batch job scheduling in grids using cellular memetic algorithms”, in 2007 IEEE International Parallel and Distributed Processing Symposium, 2007, pp. 1–8.
• [24] R. Kizys, A. Juan, B. Sawik, and L. Calvet, “A biasedrandomized iterated local search algorithm for rich portfolio optimization”, Appl. Sci. 9, 3509 (2019).
• [25] Å. Dominik et al., “Solving multi-objective job shop problem using nature-based algorithms: new pareto approximation features”, Int. J. Optim. Control, Theor. Appl. 5 (1), 1–11 (2014).
• [26] M. Kalra and S. Singh, “A review of metaheuristic scheduling techniques in cloud computing”, Egypt. Inform. J. 16 (3), 275–295 (2015).
• [27] M. Klimek and P. Łebkowski, “Financial optimisation of the scheduling for the multi-stage project”, Bull. Pol. Ac.: Tech. 65 (6), 899– 908 (2017).
• [28] K.A. Dowsland and J.M. Thompson, “Simulated annealing”, in Handbook of natural computing. pp. 1623–1655, Springer, 2012.
• [29] W. Bożejko, P. Rajba, and M. Wodecki, “Stable scheduling of single machine with probabilistic parameters”, Bull. Pol. Ac.: Tech. 65 (2), 219–231 (2017).

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).