On the Dual and Inverse Problems of Scheduling Jobs to Minimize the Maximum Penalty

What is it about?

In this paper, we consider the single-machine scheduling problem with given release datesand the objective to minimize the maximum penalty which is NP-hard in the strong sense. For thisproblem, we introduce a dual and an inverse problem and show that both these problems can besolved in polynomial time. Since the dual problem gives a lower bound on the optimal objectivefunction value of the original problem, we use the optimal function value of a sub-problem of thedual problem in a branch and bound algorithm for the original single-machine scheduling problem.We present some initial computational results for instances with up to 20 jobs.

Featured Image

Why is it important?

Good lower bounds may speed up enumerative algorithms. Moreover, it is worth to investigate whether also for other NP-hard scheduling problems, dual or inverse problems can be polynomially solved.