English

运筹学学报 ›› 2019, Vol. 23 ›› Issue (4): 105-110.doi: 10.15960/j.cnki.issn.1007-6093.2019.04.009

• • 上一篇    下一篇

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

李文华*, 翟威娜, 柴幸, 高超   

  1. 郑州大学数学与统计学院, 郑州 450001
  • 收稿日期:2018-11-26 发布日期:2019-12-04
  • 通讯作者: 李文华 E-mail:liwenhua@zzu.edu.cn
  • 基金资助:
    国家自然科学基金（Nos.11571321，11971443，11771406），河南省高等教育教改（研究生教育）（No.2019SJGLX051Y）

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

LI Wenhua*, ZHAI Weina, CHAI Xing, GAO Chao   

  1. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
  • Received:2018-11-26 Published:2019-12-04

PDF

266

摘要： 研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达，目标是最小化最大完工时间.在有界平行分批排序中，容量有限制机器最多可将b个工件形成一批同时加工，每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为√17+3/4的最好可能的在线算法.

关键词: 在线排序, 有界分批, 不相容工件族, 竞争比

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

中图分类号: