ИСТИНА

We consider single machine scheduling problems with given release dates. The objective is to minimize the maximum penalty. The problem is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problems and show that both these problems can be solved in polynomial time. The solution of the dual problem provides a lower bound of the optimal objective function value of the initial problem. Because of this, we use the optimal function value of a sub-problem of the dual problem in a branch and bound algorithm for solving the original single machine scheduling problem. Computational experiments have shown a high efficiency of the method in most cases.