期刊
MATHEMATICS
卷 8, 期 7, 页码 -出版社
MDPI
DOI: 10.3390/math8071131
关键词
single-machine scheduling; minimization of maximum penalty; dual problem; inverse problem; branch and bound
类别
资金
- RFBR [18-07-00656]
- Basic Research Program of the National Research University Higher School of Economics
In this paper, we consider the single-machine scheduling problem 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 use the optimal function value of a sub-problem of the dual 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据