工件具有任意尺寸的混合分批平行机排序问题的近似算法  

Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes

作　　者：王冬[1] 李刚刚 罗文昌[1] WANG Dong;LI Ganggang;LUO Wenchang(School of Mathematics and Statistics,Ningbo University,Ningbo 315211,Zhejiang,China;School of Information Management,Jiangxi University of Finance and Economics,Nanchang 330013,Jiangxi,China)

机构地区：[1]宁波大学数学与统计学院,浙江宁波315211 [2]江西财经大学信息管理学院,江西南昌330013

出　　处：《运筹学学报》2022年第3期133-142,共10页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11971252,11901255)。

摘　　要：本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中,一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸,每台机器可以同时处理多个工件,称为一个批,只要这些工件尺寸之和不超过其容量;一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和;目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形,为强NP-困难的。对此给出了一个(2+2α+α^(2))-近似算法,其中α为给定的权重参数,满足0≤α≤1。In this paper,we consider the mixed batch scheduling problem in which a set of jobs with arbitrary sizes should be processed on identical batch machines with identical capacities.Each job has its processing time and size.Each machine can process a group of jobs as a batch simultaneously,as long as the total size of the 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 one-dimension bin packing problem as its special case,which is strongly NPhard.For the studied problem,we provide an approximation algorithm with performance ratio of(2+2α+α^(2)),where a is a given parameter for weight with 0≤α≤1.

关 键 词：混合分批排序 工件尺寸 最大完工时间 近似算法 

分 类 号：O221.7[理学—运筹学与控制论]