中文

Operations Research Transactions >

2022 , Vol. 26 >Issue 3: 133 - 142

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.03.010

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

Expand
  • 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 date: 2022-01-20

  Online published: 2022-09-07

Fold

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.010

References

1 Potts C N , Kovalyov M Y . Scheduling with batching: A review[J]. European Journal of Operational Research, 2000, 120 (2): 228- 249.
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.
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.
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.
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.
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.
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.
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.
Options
Outlines

/

〈 〉