具有两个不相容工件族单位工件的有界分批在线排序问题

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

Abstract

Abstract: We consider on-line scheduling on a parallel batching machine with two incompatible families of unit-length jobs, where the batch capacity is bounded. In this paper, online means that jobs arrive over time. The objective is to mininize the makespan. In bounded parallel batch scheduling, a finite capacity machine can process b jobs simultaneously as a batch, and the processing time of a batch is equal to 1. Incompatible job families mean that jobs which belong to different families cannot be assigned to the same batch. For this problem, we provide a best possible online algorithm of competitive ratio √17+3/4.

Key words: on-line scheduling, bounded batching, incompatible family, competitive ratio

CLC Number:

O223

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.

[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]	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.
[4]	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.
[5]	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.
[6]	HOU Liying. Online hierarchical service scheduling on two identical machines with release times [J]. Operations Research Transactions, 2016, 20(2): 49-58.
[7]	WANG Chengfei, ZHANG Yuzhong. Online batch scheduling with known information in advance [J]. Operations Research Transactions, 2016, 20(1): 84-90.
[8]	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.
[9]	GAO Qiang, LU Xiwen. Scheduling on single machine and identical machines with rejection [J]. Operations Research Transactions, 2014, 18(4): 1-10.
[10]	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.
[11]	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.
[12]	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.
[13]	YANG Ming, LU Xi-Wen. Two-Machine Flow Shop Problems with Availability Constraints [J]. Operations Research Transactions, 2011, 15(3): 62-69.

On-line bounded-batching scheduling of unit-length jobs with two families

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 13

Recommended Articles

Metrics

Comments