Scheduling to tradeoff between the number and the length of accepted jobs.

We consider the single-machine scheduling problem to tradeoff between the number and the length of accepted jobs. The algorithm introduced by Lin and Wang (2007) (called Lin-Wang's algorithm), for solving the single-machine scheduling problem to minimize the number of tardy jobs, is closely related to our research. The original version of Lin-Wang's algorithm runs in O (n 2) time. By using the technique of the preemptive scheduling combined with a data structure, we show in this paper that a variant of Lin-Wang's algorithm actually runs in O (n log ⁡ n) time. This enables us to further show that the tradeoff problem can be solved in O (n log ⁡ n) time. [ABSTRACT FROM AUTHOR]