工件的释放时间和加工时间具有一致性的单机在线排序问题研究

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (2): 55-63.doi: 10.15960/j.cnki.issn.1007-6093.2022.02.005

工件的释放时间和加工时间具有一致性的单机在线排序问题研究

李文杰¹^,*(), 李钰晶¹, 刘海玲²

1. 洛阳师范学院数学科学学院, 河南洛阳 471934
2. 河南工程学院理学院, 河南郑州 451191

收稿日期:2021-02-26 出版日期:2022-06-15 发布日期:2022-05-27
通讯作者: 李文杰 E-mail:liwenjie0521@163.com
作者简介:李文杰 E-mail: liwenjie0521@163.com
基金资助:
河南省自然科学基金(222300420503);河南省高校重点基础研究基金(22A110015);河南省高校重点基础研究基金(20ZX004);河南省高校重点基础研究基金(22ZX009);河南省高校青年骨干教师培养计划基金(2019GGJS202);河南省高校青年骨干教师培养计划基金(2018XJGGJS-10)

Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable

Wenjie LI¹^,*(), Yujing LI¹, Hailing LIU²

1. School of Mathematical Sciences, Luoyang Normal University, Luoyang 471934, Henan, China
2. College of Science, Henan University of Engineering, Zhengzhou 451191, Henan, China

Received:2021-02-26 Online:2022-06-15 Published:2022-05-27
Contact: Wenjie LI E-mail:liwenjie0521@163.com

摘要/Abstract

摘要：

工件的释放时间和加工时间具有一致性, 是指释放时间大的工件其加工时间不小于释放时间小的工件的加工时间, 即若$r_{i}\geq r_{j}$, 则$p_{i}\geq p_{j}$。本文在该一致性约束下, 研究最小化最大加权完工时间单机在线排序问题, 和最小化总加权完工时间单机在线排序问题, 并分别设计出$\frac{\sqrt{5}+1}{2}$-竞争的最好可能在线算法。

关键词: 在线排序, 在线算法, 一致性, 加权完工时间

Abstract:

There are $n$ jobs $J_1, J_2, \cdots, J_n$ to be scheduled on the single machine. Each job $J_{j}$ has a nonnegative arriving time $r_{j}$, a positive processing time $p_{j}$, and a nonnegative weight $w_{j}$. We consider one restricted model: the jobs have agreeable release times and processing times (i.e., if $r_{i}\geq r_{j}$, then $p_{i}\geq p_{j}$). Under this restricted model, we study the single-machine online schedule to minimize the maximum weighted completion time of jobs or the total weighted completion times of jobs. We present two best possible online algorithms with the competitive ratio of both $\frac{\sqrt{5}+1}{2}$.

Key words: online scheduling, online algorithm, agreeable, weighted completion times

中图分类号:

O221.7

李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.

Wenjie LI, Yujing LI, Hailing LIU. Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable[J]. Operations Research Transactions, 2022, 26(2): 55-63.

参考文献 17

1	唐国春, 张峰, 罗守成, 刘丽丽. 现代排序论[M]. 上海: 上海科学普及出版社, 2003.
2	万国华. 排序与调度的理论、模型和算法[M]. 北京: 清华大学出版社, 2019.
3	Blazewicz J , Ecker K , Pesch E , et al. Handbook on Scheduling-From Theory to Practice[M]. Berlin: Springer, 2019.
4	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
5	Chen R B , Yuan J J . Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices[J]. 4OR-A Quarterly Journal of Operations Research, 2020, 18, 177- 196. doi: 10.1007/s10288-019-00410-4
6	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, 860- 875. doi: 10.1016/j.ejor.2019.07.072
7	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
8	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(1-10).
9	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: 1850048(1-10).
10	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, 455- 465. doi: 10.1007/s40305-017-0179-x
11	Anderson E J , Potts C N . Online scheduling of a single machine to minimize total weighted completion time[J]. Mathematics of Operations Research, 2004, 29, 686- 697. doi: 10.1287/moor.1040.0092
12	Ma R , Yuan J J . Online scheduling to minimize the total weighted completion time plus the rejection cost[J]. Journal of Combinatorial Optimization, 2017, 34, 483- 503. doi: 10.1007/s10878-016-0083-z
13	Megow N , Schulz A S . On-line scheduling to minimize average completion time revisited[J]. Operations Research Letters, 2004, 32, 485- 490. doi: 10.1016/j.orl.2003.11.008
14	Correa J R , Wagner M R . LP-based online scheduling: from single to parallel machines[J]. Mathematical Programming, 2009, 119, 109- 136. doi: 10.1007/s10107-007-0204-7
15	Tao J P . A better online algorithm for the parallel machine scheduling to minimize the weighted completion time[J]. Computer and Operations Research, 2014, 43, 215- 224. doi: 10.1016/j.cor.2013.09.016
16	Tao J P , Huang R H , Liu T D . A 2.28-competitive algorithm for online scheduling on identical machines[J]. Journal of Industrial and Management Optimization, 2015, 11, 185- 198. doi: 10.3934/jimo.2015.11.185
17	Ma R , Tao J P . An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time[J]. Journal of Industrial and Management Optimization, 2018, 14, 497- 510. doi: 10.3934/jimo.2017057

[1]	代宇波, 段懿红, 刘龙城, 王子豪. 一类一维在线单位聚类问题的随机近似算法[J]. 运筹学学报, 2022, 26(3): 143-150.
[2]	王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.
[3]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[4]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[5]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[6]	刘明熹, 甘国华, 程郁琨, 肖琳, 刘帅, 房勇. 区块链共识机制的发展现状与展望[J]. 运筹学学报, 2020, 24(1): 23-39.
[7]	薛娟, 高红伟, 姜辉, 周允旭. 基于时隙ALOHA协议的数据传输二人随机博弈模型[J]. 运筹学学报, 2019, 23(4): 45-58.
[8]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[9]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[10]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[11]	唐静静, 田英杰. 基于间隔迁移的多视角支持向量机[J]. 运筹学学报, 2018, 22(3): 1-14.
[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.

工件的释放时间和加工时间具有一致性的单机在线排序问题研究

Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 17

相关文章 15

编辑推荐

Metrics

本文评价