NDP加工模式下两个典型在线算法的性能分析
Performance Analysis of Two Typical Online Algorithms under the NDP Processing Mode
DOI: 10.12677/pm.2026.165141, PDF,    国家自然科学基金支持
作者: 李文杰：洛阳师范学院数学科学学院，河南 洛阳；杜 强：洛阳地矿双语学校，河南 洛阳；孙晓锋：洛阳师范学院文学院，河南 洛阳
关键词: 在线排序；在线算法；NDP加工模式；加权流程时间；Online Scheduling； Online Algorithm； NDP Processing Mode； Weighted Flow Time
摘要: 本文首先在NDP加工模式(即只要机器空闲且有工件可选择，则必须立即选择工件加工)下分别研究了最小化总完工时间平行机在线排序问题，并证明SPT是一个无界的在线算法。其次研究了最小化最大加权流程时间在线分批排序问题，对工件加工时间无限制情形，证明不存在常数界的在线算法；对等长工件情形，分别证明LSB是1-竞争的最优在线算法(在NDP加工模式下)和2-竞争的最好可能在线算法(在一般加工模式下)。
Abstract: This paper first studies the online scheduling problem on parallel machines to minimize the total completion time of jobs under the NDP processing mode (i.e., the available jobs cannot be delayed for processing when some machine is idle, it must be selected for processing immediately), and then prove that SPT is an unbounded online algorithm. Second, we studied the online batch- scheduling problem to minimize the maximum weighted flow times of jobs. For the case that the job processing times are unrestricted, we show that there is no online algorithm with the constant competitive ratio. For the case of equal-length jobs, we prove that LSB is a 1-competitive optimal algorithm (under the NDP processing mode) and a 2-competitive best possible online algorithm (under the general processing mode), respectively.
文章引用：李文杰, 杜强, 孙晓锋. NDP加工模式下两个典型在线算法的性能分析[J]. 理论数学, 2026, 16(5): 175-182. https://doi.org/10.12677/pm.2026.165141

参考文献

[1] 唐国春, 张峰, 罗守成, 刘丽丽. 现代排序论[M]. 上海: 上海科学普及出版社, 2003.
[2] 万国华. 排序与调度的理论、模型和算法[M]. 北京: 清华大学出版社, 2019.
[3] Blazewicz, J., Ecker, K., Pesch, E., Schmidt G., Sterna, M. and Weglarz, J. (2019) Handbook on Scheduling—From Theory to Practice. Springer.
[4] Baker, K.R. (1974) Introduction to Sequencing and Scheduling. John Wiley & Sons.
[5] Li, W. and Yuan, J. (2021) Single-Machine Online Scheduling of Jobs with Non-Delayed Processing Constraint. Journal of Combinatorial Optimization, 41, 830-843. [Google Scholar] [CrossRef] 
[6] Li, W. and Liu, H. (2023) Online NDP-Constraint Scheduling of Jobs with Delivery Times or Weights. Optimization Letters, 17, 591-612. [Google Scholar] [CrossRef] 
[7] 李文杰, 杜智慧, 苏孟龙. 加工时间与运输时间具有一致性的单机NDP约束在线排序问题研究[J]. 运筹学学报, 2024, 28(4): 18-28.
[8] Qu, Y., Tian, J., Fu, R. and Ge, K. (2024) A Best Possible Online Algorithm for Single-Machine Scheduling with Non-Delayed Processing Constraint and Bounded Delivery Times. Journal of the Operations Research Society of China. [Google Scholar] [CrossRef] 
[9] Graham, R.L., Lawler, E.L., Lenstra, J.K. and Kan, A.H.G.R. (1979) Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics, 5, 287-326. [Google Scholar] [CrossRef] 
[10] Lu, X., Sitters, R.A. and Stougie, L. (2003) A Class of On-Line Scheduling Algorithms to Minimize Total Completion Time. Operations Research Letters, 31, 232-236. [Google Scholar] [CrossRef] 
[11] Liu, P. and Lu, X. (2009) On-line Scheduling of Parallel Machines to Minimize Total Completion Times. Computers & Operations Research, 36, 2647-2652. [Google Scholar] [CrossRef] 
[12] Chai, X., Li, W. and Zhu, Y. (2021) Online Scheduling to Minimize Maximum Weighted Flow-Time on a Bounded Parallel-Batch Machine. Annals of Operations Research, 298, 79-93. [Google Scholar] [CrossRef] 
[13] Mastrolilli, M. (2004) Scheduling to Minimize Max Flow Time: Off-Line and On-Line Algorithms. International Journal of Foundations of Computer Science, 15, 385-401. [Google Scholar] [CrossRef] 
[14] Ambühl, C. and Mastrolilli, M. (2005) On-line Scheduling to Minimize Max Flow Time: An Optimal Preemptive Algorithm. Operations Research Letters, 33, 597-602. [Google Scholar] [CrossRef] 
[15] Li, W. and Yuan, J. (2011) Online Scheduling on Unbounded Parallel-Batch Machines to Minimize Maximum Flow-Time. Information Processing Letters, 111, 907-911. [Google Scholar] [CrossRef] 
[16] Jiao, C., Li, W. and Yuan, J. (2014) A Best Possible Online Algorithm for Scheduling to Minimize Maximum Flow-Time on Bounded Batch Machines. Asia-Pacific Journal of Operational Research, 31, Article ID: 1450030. [Google Scholar] [CrossRef] 
[17] Biskup, D. (1999) Single-Machine Scheduling with Learning Considerations. European Journal of Operational Research, 115, 173-178. [Google Scholar] [CrossRef] 
[18] Graham, R.L. (1966) Bounds for Certain Multiprocessing Anomalies. Bell System Technical Journal, 45, 1563-1581. [Google Scholar] [CrossRef] 

为你推荐