Beyond bin-packing combining bin-packing algorithms tailored for automated software testing: ROST-algorithm

Abstract

In this project, bin-packing has been analysed as a way of better utilizing resources in a continuous integration system in order to increase its efficiency. The worst-fit, best-fit, next-fit and first-fit algorithms have been investigated in conjunction with an optimal job scheduling approach. The many differences between bin-packing and software testing inspired a solution combining several approaches. The ROST algorithm, short for Resource-Optimized-Software-Testing algorithm was developed to be adapted to software testing. The ROST algorithm is a combination of an optimal job scheduling approach, the worst-fit and the best-fit algorithm where the algorithm changes based on the current bin capacity. The results show that it is just as good or better than the other approaches it has been compared to, and significantly better than the most common solution in continuous integration.