We address single machine problems with optional job rejection, studied lately in Zhang et al. (2010) and Cao et al. (2006) . In these papers, the authors focus on minimizing regular performance measures, i.e., functions that are non decreasing in the jobs completion time, subject to the constraint that the total rejection cost cannot exceed a predefined upper bound. The authors prove that the considered problems are ordinary NP hard and provide pseudo polynomial time Dynamic Programming (DP) solutions. In this paper, we focus on three of these problems: makespan with release dates ; total completion times; and total weighted completion, and present enhanced DPs for these problems. The resulting computational complexity achieved is O(nU), where n is the number of jobs and U is the upper bound on the total rejection cost . Moreover, the extensive numerical study we executed proves that all updated DP algorithms are extremely efficient, even for large size problem instances .
We address single machine problems with optional jobs - rejection, studied recently in Zhang et al. 21 and Cao et al. 2 . In these papers, the authors focus on minimizing regular performance measures, i.e., functions that are non-decreasing in the jobs completion time, subject to the constraint that the total rejection cost cannot exceed a predefined upper bound. They also prove that the considered problems are ordinary NP-hard and provide pseudo-polynomial-time Dynamic Programming (DP) solutions. In this paper, we focus on three of these problems: makespan with release-dates ; total completion times; and total weighted completion, and present enhanced DP solutions demonstrating both theoretical and practical improvements . Moreover, we provide extensive numerical studies verifying their efficiency .
R
job
jobs -
R
lately
recently
R
(2010)
21
R
(2006)
2
R
non decreasing
non-decreasing
R
The authors
They also
R
NP hard and provide pseudo polynomial time
NP-hard and provide pseudo-polynomial-time
R
release dates
release-dates
R
DPs for these problems. The resulting computational complexity achieved is O(nU), where n is the number of jobs and U is the upper bound on the total rejection cost
DP solutions demonstrating both theoretical and practical improvements
R
the extensive numerical study we executed proves that all updated DP algorithms are extremely efficient, even for large size problem instances
we provide extensive numerical studies verifying their efficiency