NDP约束下的最小化最大加权完工时间单机一致性在线排序问题研究
Online NDP-Constraint Scheduling of Jobs with Agreeable to Minimize the Maximum Weighted Completion Time
DOI: 10.12677/PM.2022.124067, PDF,    科研立项经费支持
作者: 李文杰, 杜智慧：洛阳师范学院，数学科学学院，河南 洛阳
关键词: 在线排序；在线算法；NDP约束；一致性；加权完工时间；Online Scheduling； Online Algorithm； NDP-Constraint； Agreeable； Weighted Completion Time
摘要: 本文在工件不能被强制推迟加工约束(即NDP约束)下研究最小化最大加权完工时间单台机器在线排序问题。每个工件Jj都具有一个释放时间rj≥0，一个加工时间pj≥0和一个权重wj≥0。每两个工件Ji和Jj的释放时间与加工时间均具有一致性，即若ri≥rj，则有pi≥pj。我们首先利用对手法构造出该排序问题的下界是1.5，其次设计出一个在线算法SLF并采用最小反例法证明其争比是1.732。
Abstract: This paper studies the single-machine online schedule under the NDP-constraint to minimize the maximum weighted completion time. Each job Jj has a release time rj≥0, a processing time pj≥0 and a weight wj≥0. Any two jobs Ji,Jj have agreeable release times and processing times (if ri≥rj, then pi≥pj). We first present a lower bound of 1.5 by the adversary method, and then design an online algorithm SLF with the competitive ratio of 1.732.
文章引用：李文杰, 杜智慧. NDP约束下的最小化最大加权完工时间单机一致性在线排序问题研究[J]. 理论数学, 2022, 12(4): 598-604. https://doi.org/10.12677/PM.2022.124067

参考文献

[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 Nature Switzerland AG, Cham. [Google Scholar] [CrossRef] 
[4] Baker, K.R. (1974) Introduction to Sequencing and Scheduling. John Wiley & Sons, New York.
[5] Li, W.J. and Yuan, J.J. (2021) Single-Machine Online Scheduling of Jobs with Non-Delayed Processing Constraint. Journal of Combinatorial Optimization, 41, 830-843. [Google Scholar] [CrossRef] 
[6] Graham, R.L., Lawer, E.L. and Lenstra, J.K. (1979) Optimiza-tion and Approximation in Deterministic Sequencing and Scheduling. Annals of Discrete Mathematics, 5, 287-326. [Google Scholar] [CrossRef] 
[7] Chai, X., Lu, L.F., Li, W.H. and Zhang, L.Q. (2018) Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time. Asia-Pacific Journal of Operational Research, 35, Article ID: 1850048. [Google Scholar] [CrossRef] 
[8] Li, W.H. and Chai, X. (2018) Online Scheduling on Bounded Batch Machines to Minimize the Maximum Weighted Completion Time. Journal of the Operations Research Society of China, 6, 455-465. [Google Scholar] [CrossRef] 
[9] Chen, R.B. and Yuan, J.J. (2020) Single-Machine Scheduling of Proportional-Linearly Deteriorating Jobs with Positional Due Indices. 4OR: A Quarterly Journal of Operations Research, 18, 177-196. [Google Scholar] [CrossRef] 
[10] Yuan, J.J., Ng, C.T. and Cheng, T.C.E. (2020) Scheduling with Release Dates and Preemption to Minimize Multiple Max-Form Objective Functions. European Journal of Operational Research, 280, 860-875. [Google Scholar] [CrossRef] 
[11] Zhao, Q.L. and Yuan, J.J. (2020) Bicriteria Scheduling of Equal Length Jobs on Uniform Parallel Machines. Journal of Combinatorial Optimization, 39, 637-661. [Google Scholar] [CrossRef] 
[12] Feng, Q. and Yuan, J.J. (2007) NP-Hardness of a Multicriteria Scheduling on Two Families of Jobs. OR Transactions, 11, 121-126.

为你推荐