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

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

Abstract

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

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]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	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.
[3]	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.
[4]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[5]	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.
[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]	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.
[10]	GAO Qiang, LU Xiwen. Scheduling on single machine and identical machines with rejection [J]. Operations Research Transactions, 2014, 18(4): 1-10.
[11]	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.
[12]	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.
[13]	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.
[14]	YANG Ming, LU Xi-Wen. Two-Machine Flow Shop Problems with Availability Constraints [J]. Operations Research Transactions, 2011, 15(3): 62-69.
[15]	WANG Cheng-Fei, ZHANG Yu-Zhong, MIAO Cui-Xia, BAI Qing-Guo. Online Batch Scheduling with Linear Deterioration Effect [J]. Operations Research Transactions, 2011, 15(3): 107-114.

Online batch scheduling with known information in advance

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments