An approximation scheme for rejection-allowed single-machine rescheduling. (August 2020)

• Record Type: Journal Article
• Authors: Luo, Wenchang; Jin, Miaomiao; Su, Bing; Lin, Guohui
• Is Part Of: Computers & industrial engineering. Volume 146(2020)
• Publication Date: 2020-08
• Subjects: Rescheduling -- Job delay -- Job rejection -- Dynamic programming -- Approximation scheme; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106574
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Consider a rescheduling problem on a single machine in response to job delays. Resource constrained where both the job rejection cost and the job tardiness are upperbounded. Explore structural properties of some optimal reschedules and design a pseudo-polynomial time. exact algorithm When the job rejection cost is unbounded, develop a fully polynomial time approximation scheme. Abstract: We study a novel rescheduling problem in which a set of jobs has been assigned an original schedule to minimize the total weighted completion time on a single machine, with the assumption but not with 100% certainty that all of them will be available when the planned processing begins. The need for rescheduling arises due to some jobs could not arrive in time; the decision-maker has to adjust the original schedule to account for the delayed jobs without causing excessive time disruption to the original schedule and to minimize their operational cost. While the decision-maker can choose to reject any of the delayed or non-delayed jobs, the total rejection cost and the tardiness of each accepted job in the adjusted schedule are strictly upper bounded by given thresholds, respectively. The total operational cost includes three components: the total weighted completion time of the accepted jobs, the total rejection cost of the rejected jobs, and the penalty on the maximum tardiness for the accepted jobs. We study this novel rescheduling problem from approximation algorithm perspective, as it generalizes several classic NP-hard scheduling problems; we design a pseudo-polynomial time dynamic programming exact algorithm and, when the total rejection cost is unbounded, we develop the exact algorithm into a fully polynomial time approximation scheme.