Minimizing flowtime and missed due-dates in single-machine sequencing (Q2640435)

The author discusses a single machine sequencing problem to minimize an objective function consisting of weighted sum of flowtime and earliness/tardiness values of each job. The main purpose of the discussed objective function is to consider a compromise between minimizing flowtime and missed due dates which reflect the customer satisfaction. The author shows that the problem belongs to the class of NP-hard problems by reducing a more restricted, but still NP-hard, sequencing problem - the Total Discrepancy Problem - to the recognition version of the discussed problem. Justified by this complexity result, the author uses a dynamic programming approach following the method of \textit{M. Held} and \textit{R. M. Karp} [SIAM J. Appl. Math. 10, 196-210 (1962; Zbl 0106.141)]. For this algorithmic approach \(n\cdot 2^{n-1}\) subproblems must be solved to find an optimal solution. Compared with an enumerative approach, which needs n! computations, the proposed approach is more efficient. But, of course, due to its exponential complexity the use of the algorithm is limited to medium size problems (up to 20 jobs).