Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty. Issue 10 (3rd October 2022) - Choi, Byung-Cheon; Park, Myoung-Ju; Min Kim, Kyung
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.