  A Variable Parameter (VP) analysis aims to give precise time complexity
expressions of algorithms with exponents appearing solely in terms of variable
parameters. A variable parameter is the number of objects with specific
properties. Here we describe two VP-algorithms, an implicit enumeration and a
polynomial-time approximation scheme for a strongly $NP$-hard problem of
scheduling $n$ independent jobs with release and due times on one machine to
minimize the maximum job completion time $C_{\max}$. Our variable parameters
are the amounts of some specially defined types of jobs. A partial solution
without these jobs is constructed in a low degree polynomial time, and an
exponential time procedure (in the number of variable parameters) is carried
out to augment it to a complete optimal solution. In the alternative time
complexity expressions, the exponential dependence is solely on the some job
parameters. Applying the fixed parameter analysis to these estimations, a
polynomial-time dependence is achieved. Both, the intuitive probabilistic
estimations and our extensive experimental study support our conjecture that
the total number of the variable parameters is far less than $n$ and its ratio
to $n$ converges to 0 asymptotically.
