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

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

Abstract

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

CLC Number:

O221

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.

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[2]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[3]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[4]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[5]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[6]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.
[7]	MIN Xiao, ZHU Junlei, LIU Jing. An online algorithm for hierarchical scheduling on two identical machines with rejection [J]. Operations Research Transactions, 2018, 22(3): 117-124.
[8]	HOU Liying. Online hierarchical service scheduling on two identical machines with release times [J]. Operations Research Transactions, 2016, 20(2): 49-58.
[9]	WANG Chengfei, ZHANG Yuzhong. Online batch scheduling with known information in advance [J]. Operations Research Transactions, 2016, 20(1): 84-90.
[10]	LI Wenhua, CHAI Xing, YUAN Hang, YANG Sufang. On-line algorithms for incompatible job families on parallel machines scheduling with lookahead [J]. Operations Research Transactions, 2015, 19(4): 121-126.
[11]	GAO Qiang, LU Xiwen. Scheduling on single machine and identical machines with rejection [J]. Operations Research Transactions, 2014, 18(4): 1-10.
[12]	YAO Ran, CHEN Guangting, ZHANG An, CHEN Yong. Preemptive online algorithms for scheduling on three machines with hierarchies [J]. Operations Research Transactions, 2013, 17(4): 63-68.
[13]	JIAO Chengwen, LI Wenhua. Online parallel batching scheduling for nonincreasing-processing-time jobs to minimize the maximum flow-time [J]. Operations Research Transactions, 2013, 17(4): 96-102.
[14]	YANG Su-Fang, LI Wen-Hua. On-line scheduling on a machine of two families with lookahead [J]. Operations Research Transactions, 2012, 16(2): 115-120.
[15]	YANG Ming, LU Xi-Wen. Two-Machine Flow Shop Problems with Availability Constraints [J]. Operations Research Transactions, 2011, 15(3): 62-69.