ИСТИНА

We study the classical NP-hard non-preemptive single machine scheduling problem to minimize the maximum penalty with release dates. Penalty of each job is a monotone and non-decreasing function of its completion time. We propose polynomial algorithms for the dual and inverse problems where the minimum penalty is maximized. Both algorithms run in quadratic time. Note that the solution values of the inverse and dual problems are valid lower bounds for the original problem. Therefore, our algorithms can be used within the branch-and-bound scheme when solving the original NP-hard problem.