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

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

Abstract

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

CLC Number:

O221.7

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.

References 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]	An ZHANG, Yong CHEN, Guangting CHEN, Zhanwen CHEN, Qiaojun SHU, Guohui LIN. Maximum matching based approximation algorithms for precedence constrained scheduling problems [J]. Operations Research Transactions, 2022, 26(3): 57-74.
[2]	Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection [J]. Operations Research Transactions, 2022, 26(2): 73-82.
[3]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[4]	Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing [J]. Operations Research Transactions, 2022, 26(1): 69-84.
[5]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[6]	Jiachen JU, Qian LIU, Zhao ZHANG, Yang ZHOU. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[7]	Libo WANG, Wenhua LI, Dan YU. Online scheduling on single batch machine with variable lookahead interval [J]. Operations Research Transactions, 2022, 26(1): 134-140.
[8]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[9]	Xiaoguang BAO, Chao LU, Dongmei HUANG, Wei YU. Approximation algorithm for min-max cycle cover problem on a mixed graph [J]. Operations Research Transactions, 2021, 25(1): 107-113.
[10]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[11]	ZHAO Congcong, FANG Dandan, LI Rongheng. Optimal algorithms for hybrid flow shop schedule on two machines with learning effect [J]. Operations Research Transactions, 2020, 24(2): 42-60.
[12]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[13]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[14]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[15]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 14

Related Articles 15

Recommended Articles

Metrics

Comments