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

Alexander A. Lazarev, Nikolay Pravdivets and Frank Werner
Additional contact information
Alexander A. Lazarev: Institute of Control Sciences, 117997 Moscow, Russia
Nikolay Pravdivets: Institute of Control Sciences, 117997 Moscow, Russia
Frank Werner: Fakultät für Mathematik, Otto-von-Guericke-Universität Magdeburg, 39106 Magdeburg, Germany

Mathematics, 2020, vol. 8, issue 7, 1-15

Abstract: 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.

Keywords: single-machine scheduling; minimization of maximum penalty; dual problem; inverse problem; branch and bound (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/7/1131/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/7/1131/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:7:p:1131-:d:382811

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().