Scheduling to tradeoff between the number and the length of accepted jobs
Scheduling to tradeoff between the number and the length of accepted jobs
复制标题
安排在接受的工作数量和长度之间进行权衡
DOI：
10.1016/j.tcs.2021.08.020
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Yuan Jinjiang
中科院分区：
文献类型：
--
作者：
Zhao Qiulan;Yuan Jinjiang
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.
