提前预知信息的在线分批排序问题

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

运筹学学报

提前预知信息的在线分批排序问题

王成飞¹ 张玉忠^1,*

1. 曲阜师范大学管理学院运筹学研究所, 山东日照 276826

收稿日期:2015-05-27 出版日期:2016-03-15 发布日期:2016-03-15
通讯作者: 张玉忠 yuzhongrz@163.com
基金资助:
教育部高等学校博士学科点专项科研基金(No. 20123705110003), 山东省自然科学基金(Nos. ZR2015GZ009, ZR2014AM012), 曲阜师范大学博士科研启动基金(No. bsqd046000051)

Online batch scheduling with known information in advance

WANG Chengfei¹ZHANG Yuzhong^1,*

1. Institute of Operations Research, College of Management, Qufu Normal University, Rizhao 276826, Shandong, China

Received:2015-05-27 Online:2016-03-15 Published:2016-03-15

摘要/Abstract

摘要：

研究工件可提前预知信息的在线分批排序问题, 工件的预知信息时间依时间到达, 目标为极小化最大完工时间. 已知从工件的信息可预知到该工件可加工需要时间~$a$, 所有工件的最大加工时间为~$p_{{\rm max}}$, 多个工件可以作为一批被机器同时加工, 批的加工时间为该批工件中最长加工时间. 对于批容量无限的单机问题给出一个在线算法~$\gamma H^\infty$, 并证明其竞争比和问题的下界都为~$1+\gamma$, 其中~$\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$, 进而算法是最优的.

关键词: 分批排序, 竞争比, 在线算法

Abstract:

We study a single online batch scheduling problem with known information in advance. The information arrives over time and the objective is to minimize the maximum completion time. The time between the information arrival of a job and its release time is constant $a$. The maximum of the processing times of all jobs $p_{{\rm max}}$ is known in advance too. A batch processing machine can handle up to $b$ jobs simultaneously. The processing time of a batch is given by the longest processing time of all jobs in the batch. When $b=\infty$, we provide an optimal online algorithm $\gamma H^\infty$ with a competitive ratio of $1+\gamma$, where $\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$.

Key words: batch scheduling, competitive ratio, online algorithm

王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2016.01.008.

WANG Chengfei, ZHANG Yuzhong. Online batch scheduling with known information in advance[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.01.008.

[1]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[3]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[4]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[5]	彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.
[6]	李英, 乔龙亮, 郑斐峰. 具有预知信息的集装箱码头泊位与岸桥联合调度在线模型[J]. 运筹学学报, 2018, 22(3): 28-36.
[7]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[8]	酒明珠, 高园, 原晋江. 工件可自由下线最小化总完工时间的平行分批排序问题[J]. 运筹学学报, 2018, 22(1): 32-41.
[9]	侯丽英. 具有服务等级的两台同型机实时在线排序[J]. 运筹学学报, 2016, 20(2): 49-58.
[10]	李文华, 柴幸, 袁航, 杨素芳. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19(4): 121-126.
[11]	高强, 鲁习文. 带有拒绝的单机和同型机排序问题[J]. 运筹学学报, 2014, 18(4): 1-10.
[12]	姚然, 陈光亭, 张安, 陈永. 具有等级约束的三台机排序问题的可中断在线算法[J]. 运筹学学报, 2013, 17(4): 63-68.
[13]	焦成文, 李文华. 工件按加工长度不增序到达的最小化最大流程在线分批排序[J]. 运筹学学报, 2013, 17(4): 96-102.
[14]	杨素芳, 李文华. 具有前瞻区间的两个工件组单机在线排序问题[J]. 运筹学学报, 2012, 16(2): 115-120.
[15]	杨名, 鲁习文. 有使用限制的二台机器流水作业问题[J]. 运筹学学报, 2011, 15(3): 62-69.

提前预知信息的在线分批排序问题

Online batch scheduling with known information in advance

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价