An algorithm for the CON due-date determination and sequencing problem (Q1097162)

For a set of n jobs with deterministic processing times and common starting times, the problem is to determine the optimal constant flow allowance \(k^*\) for the CON due-date assignment method, and the optimal sequence \(\sigma^*\) which minimizes the weighted average of missed due- dates. As \(k^*\) and \(\sigma^*\) cannot be independently determined, we propose an algorithm which systematically searches for the optimal solution. Although the algorithm has time complexity of \(O(2^ nn^ 2)\), it is considerably more efficient than the exhaustive enumeration method which considers all n! possible sequences.