  In contrast to the fixed parameter analysis (FPA), in the variable parameter
analysis (VPA) the value of the target problem parameter is not fixed, it
rather depends on the structure of a given problem instance and tends to have a
favorable asymptotic behavior when the size of the input increases. While
applying the VPA to an intractable optimization problem with $n$ objects, the
exponential-time dependence in enumeration of the feasible solution set is
attributed solely to the variable parameter $\nu$, $\nu<<n$. As opposed to the
FPA, the VPA does not imply any restriction on some problem parameters, it
rather takes an advantage of a favorable nature of the problem, which permits
to reduce the cost of enumeration of the solution space. Our main technical
contribution is a variable parameter algorithm for a strongly
$\mathsf{NP}$-hard single-machine scheduling problem to minimize maximum job
lateness. The target variable parameter $\nu$ is the number of jobs with some
specific characteristics, the ``emerging'' ones. The solution process is
separated in two phases. At phase 1 a partial solution including $n-\nu$
non-emerging jobs is constructed in a low degree polynomial time. At phase 2
less than $\nu!$ permutations of the $\nu$ emerging jobs are considered. Each
of them are incorporated into the partial schedule of phase 1. Doe to the
results of an earlier conducted experimental study, $\nu/n$ varied from $1/4$
for small problem instances to $1/10$ for the largest tested problem instances,
so that that the ratio becomes closer to 0 for large $n$s.
