• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Working paper

On the dual and inverse problems of scheduling problems with minimizing the maximum job penalty

Preprint 09/ 19, FMA, OvGU Magdeburg, 2019,. Preprint 09/ 19, FMA, OvGU Magdeburg, 2019,. Otto-von-Guericke-Universität Magdeburg, 2019
Alexander A. Lazarev, Frank Werner, Nikolay Pravdivets.
In this paper, we consider single machine scheduling problems with given release dates and the objective to minimize the maximum penalty which is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problem and show that both these problems can be solved in polynomial time. Since the dual problem gives a lower bound on the optimal objective function value of the original problem, we incorporate the optimal function value of a sub-problem of the dual problem into 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.