工件满足一致性的同类机在线分批排序问题

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

运筹学学报 ›› 2019, Vol. 23 ›› Issue (1): 111-118.doi: 10.15960/j.cnki.issn.1007-6093.2019.01.013

工件满足一致性的同类机在线分批排序问题

彭南南^*, 张玉忠, 柏庆国, 王成飞

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

收稿日期:2017-12-18 出版日期:2019-03-15 发布日期:2019-03-15
通讯作者: 彭南南 E-mail:17686601734@163.com
基金资助:
国家自然科学基金（Nos.11771251，71771138，71672166，71804089），山东省自然科学基金（No.ZR2017MG009），泰山学者工程专项经费

Online batch scheduling problem on uniform machines with agreeable processing times

PENG Nannan^*, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei

Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, Shandong, China

Received:2017-12-18 Online:2019-03-15 Published:2019-03-15

摘要/Abstract

摘要：

研究了工件满足一致性，批容量无界的两台同类机在线分批排序问题，目标为极小化工件的最大完工时间和极小化工件的最大流程时间，三元素法分别表示为Q₂|r_i < r_j⇒ p_i ≤ p_j，B=∞，on-line|C_max，Q₂|r_i < r_j⇒ p_i ≥ p_j，B=∞，on-line|F_max.不失一般性，假设第一台机器速度为1，第二台机器速度为s，s ≥ 1.对于上述两类问题设计了一个在线算法，并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α，这里α为α²+sα-1=0的正根，特别地，当s=1时，该算法的竞争比不超过1.618.对第二类排序问题，该在线算法的竞争比不超过1+1/α.

关键词: 分批排序, 在线算法, 同类机, 竞争比, 一致性

Abstract:

We study the online batch scheduling problem on two uniform machines, where the batch capacity is unbounded. When the arrival times and the processing times of jobs are agreeable, two scheduling models whose objectives are to minimize the makespan and flow-time are developed and they are expressed as Q₂|r_i < r_j⇒ p_i ≤ p_j, B=∞, on-line|C_max and Q₂|r_i < r_j⇒ p_i ≥ p_j, B=∞, on-line|F_max. Without loss of generality, the speeds of the two machines are assumed to be 1 and s,s ≥ 1. We propose an on-line algorithm and prove the competitive ratios of the algorithm are not more than s+α and 1+1/α, respectively, where α is the positive root of α²+sα-1=0. Moreover, for the former scheduling model, we prove that the competitive ratio of the algorithm is not more than 1.618, when s=1.

Key words: batch scheduling, online algorithm, uniform machine, competitive ratio, agreeable processing time

中图分类号:

O221

彭南南, 张玉忠, 柏庆国, 王成飞. 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019, 23(1): 111-118.

PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times[J]. Operations Research Transactions, 2019, 23(1): 111-118.

参考文献

[1] Zhang G C, Cai X Q, Wong C K. On-line algorithm for minimizing makespan on batch processing machines[J]. Naval Research Logistics, 2001, 48(3):241-258.
[2] Ridouard F, Ricard P, Marineau P. On-line scheduling on a batch processing machine with unbounded batch size to minimizing the makespan[J]. European Journal of Operation Research, 2008, 189(3):1327-1342.
[3] 焦成文, 李文华. 工件按加工长度不增序到达的最小化最大流程在线分批排序[J]. 运筹学学报, 2013, 17(4):96-102.
[4] 王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1):84-90.
[5] 张玉忠, 柏庆国, 徐健腾. 工件有尺寸且分两批到达的单机分批排序[J]. 运筹学报, 2006, 10(4):99-105.
[6] Fu R Y, Cheng T C E, Ng C T, et al. An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan[J]. Operations Research Letters, 2013, 41(3):216-219.
[7] 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(4):1-10.
[8] Li W H, Gao J, Yuan J J. Online-list scheduling on a single bounded parallel-batch machine to minimize makespan[J]. Asia-Pacific Journal of Operational Research, 2015, 32(4):1-15.
[9] Liu P H, Lu X W, Fang Y. A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines[J]. Journal of Scheduling, 2012, 15(1):77-81.
[10] Liu P H, Lu X W. Online unbounded batch scheduling on parallel machines with delivery times[J]. Journal of Combinatorial Optimization, 2015, 29(1):228-236.
[11] Liu H L, Yuan J J, Li W J. Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart[J]. Journal of Combinatorial Optimization, 2016, 31(4):1609-1622.
[12] Zhou H, Jiang Y W, Zhou P. Total completion time minimization scheduling on two hierarchical uniform machines[J]. Theoretical Computer Science, 2017, 702:65-76.
[13] Cao Q, Liu Z H. Semi-online scheduling with bounded job sizes on two uniform machines[J].Theoretical Computer Science, 2016, 652:1-17.
[14] Deng X T, Poon C K, Zhang Y Z. Approximation algorithms in batch processing[J]. Journal of Combinatorial Optimization, 2003, 7(3):247-257.
[15] Zhang G C, Cai X Q, Wong C K. Optimal on-line algorithms for scheduling on parallel batch processing machines[J]. ⅡE Transactions, 2003, 35(2):175-181.
[16] Ma R, Wan L, Wei L J, et al. Online bounded-batch scheduling to minimize total weighted completion time on parallel machines[J]. International Journal of Production Economics, 2014, 156:31-38.

工件满足一致性的同类机在线分批排序问题

Online batch scheduling problem on uniform machines with agreeable processing times

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[2]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[3]	刘明熹, 甘国华, 程郁琨, 肖琳, 刘帅, 房勇. 区块链共识机制的发展现状与展望[J]. 运筹学学报, 2020, 24(1): 23-39.
[4]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[5]	薛娟, 高红伟, 姜辉, 周允旭. 基于时隙ALOHA协议的数据传输二人随机博弈模型[J]. 运筹学学报, 2019, 23(4): 45-58.
[6]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[7]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[8]	唐静静, 田英杰. 基于间隔迁移的多视角支持向量机[J]. 运筹学学报, 2018, 22(3): 1-14.
[9]	李英, 乔龙亮, 郑斐峰. 具有预知信息的集装箱码头泊位与岸桥联合调度在线模型[J]. 运筹学学报, 2018, 22(3): 28-36.
[10]	闵啸，朱俊蕾，刘静. 两台带服务等级的可拒绝同型机排序问题的在线算法[J]. 运筹学学报, 2018, 22(3): 117-124.
[11]	酒明珠, 高园, 原晋江. 工件可自由下线最小化总完工时间的平行分批排序问题[J]. 运筹学学报, 2018, 22(1): 32-41.
[12]	侯丽英. 具有服务等级的两台同型机实时在线排序[J]. 运筹学学报, 2016, 20(2): 49-58.
[13]	王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1): 84-90.
[14]	李文华, 柴幸, 袁航, 杨素芳. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19(4): 121-126.
[15]	高强, 鲁习文. 带有拒绝的单机和同型机排序问题[J]. 运筹学学报, 2014, 18(4): 1-10.