English

运筹学学报（中英文） ›› 2026, Vol. 30 ›› Issue (1): 188-196.doi: 10.15960/j.cnki.issn.1007-6093.2026.01.013

• • 上一篇    

嵌套加工型限制下的混合分批平行机排序问题的近似算法

吴弘一1, 王冬1, 万龙2, 罗文昌1,†   

  1. 1. 宁波大学数学与统计学院, 浙江宁波 315211;
    2. 江西财经大学信息管理学院, 江西南昌 330013
  • 收稿日期:2022-12-22 发布日期:2026-03-16
  • 通讯作者: 罗文昌 E-mail:luowenchang@163.com
  • 基金资助:
    国家自然科学基金 (Nos. 11971252, 12261039)

Approximation algorithm for mixed batch parallel machine scheduling with nested processing set restrictions

WU Hongyi1, WANG Dong1, WAN Long2, LUO Wenchang1,†   

  1. 1. School of Mathematics and Statistics, Ningbo University, Ningbo 315211, Zhejiang, China;
    2. School of Information Management, Jiangxi University of Finance and Economics, Nanchang 330013, Jiangxi, China
  • Received:2022-12-22 Published:2026-03-16

PDF

2

摘要： 本文研究了加工工件的机器集具有嵌套型限制下的混合分批平行机排序问题。具体来说, 给定一个待加工的工件集需在多台平行批处理机中的一台进行加工,每个工件有它的加工时间和可加工它的机器集,这些机器集之间满足嵌套型加工限制; 每台机器可以同时加工多个工件,称为一个批次, 只要批内工件总个数不超过其容量即可;一个批次的加工时间等于该批中工件的最大加工时间与总加工时间的加权和;目标函数是极小化最大完工时间。该问题包含经典的平行机排序问题为其特殊情形, 为强NP-困难的。对此设计了一个性能比为 $\left({2 + \alpha} \right)$ 的近似算法,其中$\alpha$ 为给定的权重参数, 满足$0\leq\alpha\leq 1$。

关键词: 混合分批排序, 嵌套加工型, 最大完工时间, 近似算法

Abstract: In this paper, we investigate the mixed batch parallel machine scheduling problem in which a set of jobs should be processed on one of the parallel batch machines with nested processing set restrictions. Each job has its processing time and its machine set for processing with these machine sets satisfying the nested processing set restrictions. Each machine can process a group of jobs as a batch simultaneously, as long as the total number of jobs in this batch does not exceed the capacity of the machine. For a given batch, its processing time is equal to the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective function is to minimize the makespan. The problem includes the classic parallel machine scheduling problem as a special case, which is strongly NP-hard. For the studied problem, we derive an approximation algorithm with a performance ratio of $\left({2 + \alpha} \right)$, where $\alpha$ is a given parameter for weight with $0\leq\alpha\leq 1$.

Key words: mixed batch scheduling, nested processing set, makespan, approximation algorithm

中图分类号: