  We consider the problem of scheduling $n$ jobs to minimize the makespan on
$m$ unrelated machines, where job $j$ requires time $p_{ij}$ if processed on
machine $i$. A classic algorithm of Lenstra et al. yields the best known
approximation ratio of $2$ for the problem. Improving this bound has been a
prominent open problem for over two decades. In this paper we obtain a tighter
bound for a wide subclass of instances which can be identified efficiently.
Specifically, we define the feasibility factor of a given instance as the
minimum fraction of machines on which each job can be processed. We show that
there is a polynomial-time algorithm that, given values $L$ and $T$, and an
instance having a sufficiently large feasibility factor $h \in (0,1]$, either
proves that no schedule of mean machine completion time $L$ and makespan $T$
exists, or else finds a schedule of makespan at most $T + L/h < 2T$. For the
restricted version of the problem, where for each job $j$ and machine $i$,
$p_{ij} \in \{p_j, \infty\}$, we show that a simpler algorithm yields a better
bound, thus improving for highly feasible instances the best known ratio of
$33/17 + \epsilon$, for any fixed $\epsilon >0$, due to Svensson.
