Open AccessA Single-machine Scheduling with Generalized Due Dates to Minimize Total Weighted Late Work
Author(s) -
Myoung-Ju Park,
Byung-Cheon Choi
Publication year - 2022
Publication title -
asian research journal of mathematics
Language(s) - English
Resource type - Journals
ISSN - 2456-477X
DOI - 10.9734/arjom/2022/v18i430368
Subject(s) - single machine scheduling , scheduling (production processes) , mathematical optimization , computer science , work (physics) , mathematics , job shop scheduling , algorithm , combinatorics , engineering , schedule , operating system , mechanical engineering
In the paper, we consider a single-machine scheduling problem with generalized due dates, in which the objective is to minimize total weighted work. This problem was proven to be NP-hard by Mosheiov et al. [1]. However, the exact complexity remains open. We show that the problem is strongly NP-hard, and is weakly NP-hard if the lengths of the intervals between the consecutive due dates are identical.