Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty. Issue 10 (3rd October 2022)

• Record Type: Journal Article
• Authors: Choi, Byung-Cheon; Park, Myoung-Ju; Min Kim, Kyung
• Is Part Of: Engineering optimization. Volume 54:Issue 10(2022)
• Page Start: 1773
• Page End: 1786
• Publication Date: 2022-10-03
• Subjects: Scheduling -- NP-hardness -- generalized due dates -- genetic algorithm; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2021.2014477
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : This article considers the min–max version of a single-machine scheduling problem with generalized due dates under processing time uncertainty. The objective is to minimize the maximum number of tardy jobs over all scenarios. For a problem with a common due date, denoted d, it is shown that the case with a fixed number of scenarios is weakly NP-hard and has no fully polynomial time approximation scheme, although it has a polynomial time approximation scheme. Furthermore, it is shown that the case with an arbitrary number of scenarios has no α -approximation algorithm for any constant 1 < α < d . For a problem with identical due date intervals, it is shown that the case with two scenarios is strongly NP-hard and has no α -approximation algorithm for any constant α > 1 . As a practical solution approach, a genetic algorithm is proposed and numerical experiments are conducted to verify its performance.