On the equivalence of single machine earliness/tardiness problems with job rejection
Article
Koulamas, C, Panwalkar, SS. (2015). On the equivalence of single machine earliness/tardiness problems with job rejection
. COMPUTERS & INDUSTRIAL ENGINEERING, 87 1-3. 10.1016/j.cie.2015.04.014
Koulamas, C, Panwalkar, SS. (2015). On the equivalence of single machine earliness/tardiness problems with job rejection
. COMPUTERS & INDUSTRIAL ENGINEERING, 87 1-3. 10.1016/j.cie.2015.04.014
We present optimal algorithms for single-machine scheduling problems with earliness criteria and job rejection and compare them with the algorithms for the corresponding problems with tardiness objectives. We present an optimal O(n log n) algorithm for minimizing the maximum earliness on a single machine with job rejection. Our algorithm also solves the bi-criteria scheduling problem is which the objective is to simultaneously minimize the maximum earliness of the scheduled jobs and the total rejection cost of the rejected jobs. We also show that the optimal pseudo-polynomial time algorithm for the total tardiness problem with job rejection can be used to solve the corresponding total earliness problem with job rejection.
