| 具有两个不相容工件族单位工件的有界分批在线排序问题 |
| |
| 引用本文： | 李文华,翟威娜,柴幸,高超.具有两个不相容工件族单位工件的有界分批在线排序问题[J].运筹学学报,2010,23(4):105-110. |
| |
| 作者姓名： | 李文华 翟威娜 柴幸 高超 |
| |
| 作者单位： | 郑州大学数学与统计学院, 郑州 450001 |
| |
| 基金项目： | 国家自然科学基金（Nos.11571321，11971443，11771406），河南省高等教育教改（研究生教育）（No.2019SJGLX051Y） |
| |
| 摘 要： | 研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达，目标是最小化最大完工时间.在有界平行分批排序中，容量有限制机器最多可将b个工件形成一批同时加工，每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为√17+3/4的最好可能的在线算法.
|
| 关 键 词： | 在线排序 有界分批 不相容工件族 竞争比 |
| 收稿时间： | 2018-11-26 |
On-line bounded-batching scheduling of unit-length jobs with two families |
| |
| LI Wenhua,ZHAI Weina,CHAI Xing,GAO Chao.On-line bounded-batching scheduling of unit-length jobs with two families[J].OR Transactions,2010,23(4):105-110. |
| |
| Authors: | LI Wenhua ZHAI Weina CHAI Xing GAO Chao |
| |
| Institution: | School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China |
| |
| 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. |
| |
| Keywords: | on-line scheduling bounded batching incompatible family competitive ratio |
|
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
