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

doi:10.15960/j.cnki.issn.1007-6093.2022.03.010

运筹学学报 ›› 2022, Vol. 26 ›› Issue (3): 133-142.doi: 10.15960/j.cnki.issn.1007-6093.2022.03.010

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

王冬¹, 李刚刚², 罗文昌¹^,*()

1. 宁波大学数学与统计学院, 浙江宁波 315211
2. 江西财经大学信息管理学院, 江西南昌 330013

收稿日期:2022-01-20 出版日期:2022-09-15 发布日期:2022-09-07
通讯作者: 罗文昌 E-mail:luowenchang@163.com
作者简介:罗文昌, E-mail: luowenchang@163.com
基金资助:
国家自然科学基金(11971252);国家自然科学基金(11901255)

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

Dong WANG¹, Ganggang LI², Wenchang LUO¹^,*()

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-01-20 Online:2022-09-15 Published:2022-09-07
Contact: Wenchang LUO E-mail:luowenchang@163.com

摘要/Abstract

摘要：

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足$0\leq\alpha\leq 1$。

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

Abstract:

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 NP-hard. For the studied problem, we provide an approximation algorithm with performance ratio of $\left( {2 +2\alpha+\alpha^{2}} \right)$, where $\alpha$ is a given parameter for weight with $0\leq\alpha\leq 1$.

Key words: mixed batch scheduling, job size, makespan, approximation algorithm

中图分类号:

O221.7

王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.

Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes[J]. Operations Research Transactions, 2022, 26(3): 133-142.

参考文献 14

1	Potts C N , Kovalyov M Y . Scheduling with batching: A review[J]. European Journal of Operational Research, 2000, 120 (2): 228- 249. doi: 10.1016/S0377-2217(99)00153-8
2	Mathirajan M , Sivakumar A I . A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor[J]. The International Journal of Advanced Manufacturing Technology, 2006, 29 (9/10): 990- 1001.
3	Wang J Q , Fan G Q , Liu Z . Mixed batch scheduling on identical machines[J]. Journal of Scheduling, 2020, 23 (4): 487- 496. doi: 10.1007/s10951-019-00623-9
4	Graham R L , Lawler E L , Lenstra J K , et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5, 236- 287.
5	Coffman E G , Garey M R , Johnson D S . Approximation Algorithms for Bin Packing: A Survey[M]. Boston: PWS, 1996: 46- 93.
6	Garey M R , Johnson D S . Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. San Francisco: Freeman, 1979.
7	Lee CY , Uzsoy R , Martin-Vega LA . Efficient algorithms for scheduling semiconductor burn-in operations[J]. Operations Research, 1992, 40 (4): 764- 775. doi: 10.1287/opre.40.4.764
8	Uzsoy R . Scheduling a single batch processing machine with non-identical job sizes[J]. The International Journal of Production Research, 1994, 32 (7): 1615- 1635. doi: 10.1080/00207549408957026
9	Zhang G , Cai X , Lee C Y , et al. Minimizing makespan on a single batch processing machine with nonidentical job sizes[J]. Naval Research Logistics, 2001, 48 (3): 226- 240. doi: 10.1002/nav.4
10	Dosa G , Tan Z , Tuza Z , et al. Improved bounds for batch scheduling with nonidentical job sizes[J]. Naval Research Logistics, 2014, 61 (5): 351- 358. doi: 10.1002/nav.21587
11	Li S . Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities[J]. European Journal of Operational Research, 2017, 263 (3): 815- 826. doi: 10.1016/j.ejor.2017.06.021
12	Hochbaum D S , Shmoys D B . Using dual approximation algorithms for scheduling problems: Theoretical and practical results[J]. Journal of the ACM, 1987, 34 (1): 144- 162.
13	Fan G Q , Wang J Q , Liu Z . Two-agent scheduling on mixed batch machines to minimise the total weighted makespan[J]. International Journal of Production Research, 2020, (2): 1- 20.
14	Deng X , Feng H , Li G , et al. A PTAS for semiconductor burn-in scheduling[J]. Journal of Combinatorial Optimization, 2005, 9 (1): 5- 17.

[1]	袁藩, 徐大川, 张冬梅. k-均值问题的差分隐私算法综述[J]. 运筹学学报, 2022, 26(3): 1-16.
[2]	张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.
[3]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[4]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[5]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[6]	刘文杰, 张冬梅, 张鹏, 邹娟. 带惩罚μ-相似Bregman散度k-均值问题的初始化算法[J]. 运筹学学报, 2022, 26(1): 99-112.
[7]	剧嘉琛, 刘茜, 张昭, 周洋. 带惩罚的相同容量k-均值问题的局部搜索算法[J]. 运筹学学报, 2022, 26(1): 113-124.
[8]	李小玮, 成夏炎, 李荣珩. 带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法[J]. 运筹学学报, 2021, 25(4): 31-44.
[9]	包晓光, 路超, 黄冬梅, 余炜. 混合图上最小-最大圈覆盖问题的近似算法[J]. 运筹学学报, 2021, 25(1): 107-113.
[10]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[11]	赵聪聪, 方丹丹, 李荣珩. 具有学习效应的两台机上最优混合流水作业算法[J]. 运筹学学报, 2020, 24(2): 42-60.
[12]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[13]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[14]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[15]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 14

相关文章 15

编辑推荐

Metrics

本文评价