# How to test which of two scheduling strategies perform better based on data with unknown distribution

Having two scheduling strategies, I'd like to test which one performs better. The input data (several problem test cases) for the strategies are randomly generated. The strategies are used to compute an optimal feasible schedule. During the scheduling, several things are measured: scheduling time, number of backtracks performed, number of nodes in the search tree, and other criteria. I'd like to compare the strategies at each of the criteria.

I can't determine any distribution for the measured data. Moreover, the data might strongly differ for each test case. For example, the scheduling times might be:

| test case  | strategy #1 | strategy #2 |
|------------|-------------|-------------|
| #1         |         300 |         500 |
| #2         |        1200 |        3300 |
| #3         |         150 |         140 |
| #4         |        2340 |        6872 |
| #5         |        4354 |        9335 |
| #6         |         972 |         869 |


Is there a test statistic I can use to perform a hypothesis test such as: "strategy #1 runs faster than strategy #2"? What is the best way to measure which of the two strategies performs better at a criterion?

-

Since you don't know anything about the distribution the test cases are (presumably) generated from, all you really have to go on is which algorithm wins in each test case. Ignore any test cases (hopefully there won't be many) where the algorithms are tied. Let $N$ be the number of test cases where there is a winner, and $X$ the number of these where algorithm A wins. Given $N = n$, $X$ should be binomial with parameters $n$ and $p$, $p$ being the (unknown) probability of algorithm A winning a test case. If your null hypothesis is that A is no better than B, you can reject the null hypothesis at level $\alpha$ if $X \ge x(N)$ where the binomial distribution with parameters $N$ and $p=1/2$ would make $P(X \ge x(N)) < \alpha$. For large $n$ you could use the normal approximation to the binomial.