工件权重带限制的最小化最大加权完工时间的单机在线排序问题

doi:10.15960/j.cnki.issn.1007-6093.2024.02.005

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (2): 71-80.doi: 10.15960/j.cnki.issn.1007-6093.2024.02.005

工件权重带限制的最小化最大加权完工时间的单机在线排序问题

徐娟年¹, 马冉¹^,*(), 韩雯雯¹, 张玉忠²

1. 青岛理工大学管理工程学院, 山东青岛 266525
2. 曲阜师范大学管理学院、运筹学研究院, 山东日照 276826

收稿日期:2021-06-23 出版日期:2024-06-15 发布日期:2024-06-07
通讯作者: 马冉 E-mail:sungirlmr@126.com
基金资助:
国家自然科学基金(11501171);国家自然科学基金(11771251);山东省自然科学基金(ZR2020MA028)

Single-machine online scheduling to minimize maximum weighted completion time with limited weights

Juannian XU¹, Ran MA¹^,*(), Wenwen HAN¹, Yuzhong ZHANG²

1. School of Management Engineering, Qingdao University of Technology, Qingdao 266525, Shandong, China
2. Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, Shandong, China

Received:2021-06-23 Online:2024-06-15 Published:2024-06-07
Contact: Ran MA E-mail:sungirlmr@126.com

摘要/Abstract

摘要：

本文考虑了最小化最大加权完工时间的单机在线排序问题, 要求工件的权重在工件加工时间一定范围之内且工件的权重和工件加工时间具有一致性, 即$ ap_j\leq w_j\leq bp_j (a\geq\frac{\sqrt{5}-1}{2}b, b\geq a)$且若$ w_i>w_j$则$ p_i\geq p_j$, 如果$ w_i=w_j$则$ p_i=p_j$。工件以时间在线的方式到达, 只有工件$ J_j$在达到释放时间$ r_j$后, 决策者才知晓工件的基本信息, 如加工时间$ p_j$和权重$ w_j$。对于此问题, 首先利用对手法证明了其下界为$ 1+\frac{b}{b+a}$, 随后给出了竞争比为$ 1+\frac{b}{b+a}$的最好可能的在线算法。特别地, 当$ a=\frac{\sqrt{5}-1}{2}b$时, 该算法的竞争比为$ \frac{\sqrt{5}+1}{2}$。

关键词: 单机, 在线排序, 在线算法, 加权完工时间

Abstract:

The setting we consider is nonpreemptive single machine online scheduling, with the objective to minimize the maximum weighted completion time of jobs. The weight of the job is not only limited strictly within the processing time compass of this job, but also agreeable with processing time of this job, i.e., $ ap_j\leq w_j\leq bp_j(a\geq\frac{\sqrt{5}-1}{2}b, b\geq a)$ and if $ w_i>w_j$, then $ p_i\geq p_j$. Especially, if $ w_i=w_j$, then $ p_i=p_j$. Significantly, there are irrelevant jobs arriving online over time and the knowledge of each job $ J_j$, such as its processing length $ p_j$ and weight $ w_j$, is not revealed for the scheduler until it is released at time $ r_j$. By means of adversary method, it is explicitly derived that the lower bound of the considered problem is $ 1+\frac{b}{b+a}$. Then we provide a best possible online algorithm with the competitive ratio of $ 1+\frac{b}{b+a}$. Moreover, the competitive ratio of this algorithm is $ \frac{\sqrt5+1}{2}$, when $ a=\frac{\sqrt{5}-1}{2}b$.

Key words: single machine, online scheduling, online algorithm, weighted completion time

中图分类号:

O221.2

徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.

Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG. Single-machine online scheduling to minimize maximum weighted completion time with limited weights[J]. Operations Research Transactions, 2024, 28(2): 71-80.

图/表 2

参考文献 14

1	Vestjens A P A. On-line machine scheduling[D]. Netherlands: Eindhove University of Technology, 1997.
2	Pruhs K, Sgall J, Tong E. Online scheduling[M]//Handbook of Scheduling: Algorithms, Model, and Pertormance Analysis, Boca Raton: Chapman and Hall/CRC Press, 2004: 1-41.
3	Tan Z Y, Zhang A. Online and semi-online scheduling[M]//Handbook of Combinatorial Optimization, New York: Springer, 2013.
4	Tian J , Fu R Y , Yuan J J . Online over time scheduling on parallel-batch machines: A survey[J]. Journal of the Operations Research Society of China, 2014, 2, 445- 454. doi: 10.1007/s40305-014-0060-0
5	Tang L X , Li F , Zhen Z L . Integrated scheduling of production and two-stage delivery of make-to-order products: Offline and online algorithms[J]. Informs Journal on Computing, 2019, 31 (3): 493- 514. doi: 10.1287/ijoc.2018.0842
6	冯琪, 原晋江. 一个具有两类工件的多目标排序的NP-困难性[J]. 运筹学学报, 2007, 11 (4): 121- 126.
7	Oron D , Shabtay D , Steiner G . Single machine scheduling with two competing agents and equal job processing times[J]. European Journal of Operational Research, 2015, 244, 86- 99. doi: 10.1016/j.ejor.2015.01.003
8	Chen R B , Yuan J J . Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices[J]. 4OR, 2020, 18 (2): 177- 196. doi: 10.1007/s10288-019-00410-4
9	Yuan J J , Ng C T , Cheng T C E . Scheduling with release dates and preemption to minimize multiple max-form objective functions[J]. European Journal of Operational Research, 2020, 280 (3): 860- 875. doi: 10.1016/j.ejor.2019.07.072
10	Zhao Q L , Yuan J J . Bicriteria scheduling of equal length jobs on uniform parallel machines[J]. Journal of Combinatorial Optimization, 2020, 39, 637- 661. doi: 10.1007/s10878-019-00507-w
11	Li W J . A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time[J]. Asia-Pacific Journal of Operational Research, 2015, 32, 1550030. doi: 10.1142/S021759591550030X
12	Chai X , Lu L F , Li W H , et al. Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time[J]. Asia-Pacific Journal of Operational Research, 2018, 35 (6): 1850048. doi: 10.1142/S0217595918500483
13	Li W H , Chai X . Online scheduling on bounded batch machines to minimize the maximum weighted completion time[J]. Journal of the Operations Research Society of China, 2018, 6 (3): 455- 465. doi: 10.1007/s40305-017-0179-x
14	Li W J , Yuan J J . Single-machine online scheduling of jobs with non-delayed processing constraint[J]. Journal of Combinatorial Optimization, 2021, 41, 830- 843. doi: 10.1007/s10878-021-00722-4

[1]	吴琼, 王长军. 基于拉格朗日松弛的产能共享讨价还价研究[J]. 运筹学学报（中英文）, 2024, 28(2): 93-102.
[2]	代宇波, 段懿红, 刘龙城, 王子豪. 一类一维在线单位聚类问题的随机近似算法[J]. 运筹学学报, 2022, 26(3): 143-150.
[3]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[4]	王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.
[5]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[6]	徐晨, 徐寅峰, 郑斐峰. 考虑部分工件不可打扰的多任务调度问题研究[J]. 运筹学学报, 2021, 25(4): 91-100.
[7]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[8]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[9]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[10]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[11]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[12]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[13]	侯丽英. 具有服务等级的两台同型机实时在线排序[J]. 运筹学学报, 2016, 20(2): 49-58.
[14]	王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1): 84-90.
[15]	李文华, 柴幸, 袁航, 杨素芳. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19(4): 121-126.

工件权重带限制的最小化最大加权完工时间的单机在线排序问题

Single-machine online scheduling to minimize maximum weighted completion time with limited weights

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 14

相关文章 15

编辑推荐

Metrics

本文评价