Compact enumeration for scheduling one machine

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}$. Thus variable parameters are 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 (in the number of variable parameters) procedure is carried out to augment this solution to a complete optimal solution. We also give alternative time complexity expressions, where the exponential dependence is solely on some job parameters. Applying the fixed parameter analysis to these estimations, unexpectedly, we obtain a polynomial-time dependence. Both, 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$ asymptotically converges to 0.