A Single-machine Scheduling with Generalized Due Dates to Minimize Total Weighted Late Work
Myoung-Ju Park
Department of Industrial and Management Systems Engineering, Kyung Hee University, 1732, Deogyeong-daero, Giheung-gu, Yongin-si, Kyunggi-do 17104, Korea.
Byung-Cheon Choi *
School of Business, Chungnam National University, 99 Daehak-ro, Yuseong-gu, Daejeon 34134, Korea.
*Author to whom correspondence should be addressed.
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.
Keywords: Scheduling, total late work, generalized due dates, computational complexity