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

• 作 者: 李文华 翟威娜 柴幸 高超
• 机 构: 郑州大学数学与统计学院
• 出 处: 运筹学学报
• 发表日期: 2019年4期
• 关键词: 在线排序 有界分批 不相容工件族 竞争比 on-line scheduling bounded batching incompatible family com
• 基金项目: 国家自然科学基金(Nos.11571321,11971443,11771406),河南省高等教育教改(研究生教育)(No.2019SJGLX051Y)

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