摘要
研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在有界平行分批排序中,容量有限制机器最多可将b个工件形成一批同时加工,每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为/17+3/4的最好可能的在线算法.
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.
作者
李文华
翟威娜
柴幸
高超
LI Wenhua;ZHAI Weina;CHAI Xing;GAO Chao(School of Mathematics and Statistics,Zhengzhou Univer-sity,Zhengzhou 450001,China)
出处
《运筹学学报》
北大核心
2019年第4期105-110,共6页
Operations Research Transactions
基金
国家自然科学基金(Nos.11571321,11971443,11771406)
河南省高等教育教改(研究生教育)(No.2019SJGLX051Y)
关键词
在线排序
有界分批
不相容工件族
竞争比
on-line scheduling
bounded batching
incompatible family
competitive ratio
