A Single-machine Scheduling with Generalized Due Dates to Minimize Total Weighted Late Work

Park, Myoung-Ju and Choi, Byung-Cheon (2022) A Single-machine Scheduling with Generalized Due Dates to Minimize Total Weighted Late Work. Asian Research Journal of Mathematics, 18 (4). pp. 1-6. ISSN 2456-477X

[thumbnail of 539-Article Text-958-1-10-20220929.pdf] Text
539-Article Text-958-1-10-20220929.pdf - Published Version
Download (133kB)

Abstract

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.

Item Type: Article
Subjects: Academic Digital Library > Mathematical Science
Depositing User: Unnamed user with email info@academicdigitallibrary.org
Date Deposited: 12 Jan 2023 08:03
Last Modified: 27 Feb 2024 04:26
URI: http://publications.article4sub.com/id/eprint/355

Actions (login required)

View Item
View Item