Ok, you are mjd so I shouldn't probably "dare" to comment, but...

use Getopt::Std;
[download]

I personally believe that since we recommend newbies and more expert programmers altogether to always use strict and warnings, and this is a nice little utility likely to be picked up as an example, it would be a good thing if it had

use strict;
use warnings;
[download]

at the top. So to build a better future for our children...

Also,

use List::Util 'shuffle';
[download]

would implement the -r switch straight ahead.

getopts('r:n:v', \%opt) or usage();
[download]

The docs do not say anything about getopts() return value, and indeed experimental evidence is that it can't be relied upon for failure checking. Suitable hooks are provided instead, although admittedly I don't like the interface. (Suitably named subs in main::)

sub usage {
  print STDERR "Usage: $0 [-n N] [-r] [-v] command arg1 arg2...
Run command arg1, command arg2, etc., concurrently.
Run no more than N processes simultaneously (default 1)
    -r: run commands in random order instead of specified order (unimp
+l.)
    -v: verbose mode
";
  exit 1;
[download]

Any good reason for basically reimplementing die? Incidentally, I would have used a here-doc instead. Personally, I like to implement a USAGE sub like thus:

sub USAGE () {
    my $name=basename $0;  # File::Basename's
    <<".EOT";
Usage: $name [args]
[actual usage here]
.EOT
}
[download]

So if the user explicitly asks for help, then I print to STDOUT and exit regularly, for in that case I wouldn't consider the program termination to be "abnormal". Else, I regularly die USAGE.