@stefanv travis-ci has one only one core per virtual machine where the builds are running. So using it won't speed up the scikit-image build. Separate travis-ci builds and starting the slowest one first is the best option, I think. It's what others like e.g. https://travis-ci.org/astropy/astropy/ do.