Back to Search
Start Over
Scheduling to tradeoff between the number and the length of accepted jobs.
- Source :
-
Theoretical Computer Science . Nov2021, Vol. 891, p24-34. 11p. - Publication Year :
- 2021
-
Abstract
- 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]
- Subjects :
- *ALGORITHMS
*SCHEDULING
*DATA structures
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 891
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 153034671
- Full Text :
- https://doi.org/10.1016/j.tcs.2021.08.020