Uniform Machine Scheduling Problem with Deteriorating Jobs and Rejection

• DOI: 10.4028/www.scientific.net/amm.433-435.2429
• Publication Date: 2013-10-15T14:57:01Z
• Authors: Sheng Hua Zhao; Cheng Xin Luo
• Keywords: Single-machine scheduling; Penalty Method

In this paper, we consider uniform machine scheduling problem with deteriorating jobs and rejection. Each job's processing time is a linear nondecreasing function of its starting time. A job can be rejected by paying penalty cost. The objective to minimize the sum makespan accepted total rejection jobs. We propose fully polynomial-time approximation scheme (FPTAS), which shows that NP-hard in ordinary sense.