Permutation tests contain random components in the procedure (more details: biomarker analysis, PLS-DA). The results may be different in each run. In our experience, the variations should be usually small when you have a large number of samples (at least 40 samples with balance design).
If the differences are large, consider the following:
- Sample size is too small
- Very unbalanced group
- Potential outliers which lead to unstable models