Testfallsprioritering som ett matematiskt schemaläggningsproblem

Software testing is an extremely important phase of product development where the objective is to detect hidden bugs. The usually high complexity of today’s products makes the testing very resource intensive since numerous test cases have to be generated in order to detect all potential faults. Therefore, improved strategies of the testing process is of high interest for many companies. One area where there exists potential for improvement is the order by which test cases are executed to detect faults as quickly as possible, which in research is known as the test case prioritization problem. In this thesis, an extension to this problem is studied where dependencies between test cases are present and the processing times of the test cases are known. As a first result of the thesis, a mathematical model of the test case prioritization problem with dependencies and known processing times as a mathematical scheduling problem is presented. Three different solution algorithms to this problem are subsequently evaluated: A Sidney decomposition algorithm, an own-designed heuristic algorithm and an algorithm based on Smith’s rule. The Sidney decomposition algorithm outper-formed the others in terms of execution time of the algorithm and objective value of the generated schedule. The evaluation was conducted by simulation with artificial test suites and via a case study in industry through a company in the railway domain.Mjukvarutestning är en extremt viktigt fas i produktutveckling då det säkerställer att inga buggar finns i mjukvaran. Då nutidens produkter ofta inkluderar en komplex mjukvara, kräver mjukvarutestningen mer resurser än tidigare. Eftersom komplexiteten kräver att fler testfall för mjukvaran definieras för att upptäcka eventuella buggar. Detta har skapat ett stort intresse hos företag för strategier inom delområden av mjukvarutestning som syftar till att effektivisera och förenkla desamma. Ett av dessa uppmärksammade delområden är i vilken ordning testfallen ska utföras i syfte att upptäcka buggar i ett så tidigt skede som möjligt, vilket i litteraturen är känt som prioriteringsproblemet för testfall. I den här uppsatsen studeras en utökad version av prioriteringsproblemet där det existerar företrädesberoenden mellan testfallen samt att tiden det tar att exekvera ett testfall är känd. Som ett första delresultat presenteras en matematisk modell av detta utökade problem i form av ett matematiskt schemaläggningsproblem. Sedermera jämförs tre lösningsmetoder för denna modell. Lösningsmetoderna som jämförs är Sidneys upplösningsmetod, en egendesignad metod samt en metod baserad på Smiths regel. Sidneys upplösningsmetod var den metod som gav bäst resultat avseende både exekveringstid och numeriskt resultat. Jämförelsen genomfördes genom simulering av flera artificiellt skapade testfall samt genom en fallstudie på ett företag i järnvägsindustrin