Ah, a topological sort. Which you can be reduced to sorting if there are no conflicting requirements. (Sometimes you can do a topological sort faster than an ordinary sort, but you never need more time than a regular sort).

I'd preprocess the 'pred' arrays so I can faster search in them, after that, I'd do a regular sort:

#!/usr/bin/perl

use strict; 
use warnings;   
        
my %hash = (
    MEX1J  =>  {
        desc  =>  'Job 2',
        pred  =>  [qw /TEX1J/],
    },
    MEX2J  =>  {
        desc  =>  'Job End',
        pred  =>  [qw /TEX1J MEX1J/],
    },
    TEX1J  =>  {
        desc  =>  'Job start',
        pred  =>  [],
    },
);
 
#
# Preprocess, transform the 'pred' arrays into hashes.   
#
while (my ($key, $value) = each %hash) {
    $value->{pred_h} = {map {($_, 1)} @{$value->{pred}}};
}
 
#
# Sort keys.
#
my @keys = sort {$hash{$b}{pred_h}{$a} ? -1 :
                 $hash{$a}{pred_h}{$b} ?  1 : 0} keys %hash;
 
#
# Print keys.
#
print "$_\n" for @keys;

__END__
TEX1J
MEX1J
MEX2J
[download]

Note that you can write the sort block as:

{$hash{$a}{pred_h}{$b} - $hash{$b}{pred_h}{$a}}
[download]

but that's rather obscure, and you'd need to turn off warnings.