This paper studies a hierarchical optimization problem of scheduling n jobs on a serial-batching machine, in which two objective functions are maximum costs. By a hierarchical optimization problem, we mean the problem of optimizing the secondary criterion under the constraint that the primary criterion is optimized. A serial-batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We confine ourselves to the bounded model, where b < n. We present an O(n4)-time algorithm for this hierarchical optimization problem. For the special case where two objective functions are maximum lateness, we give an O(n3 log n)-time algorithm.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2020144
Keywords: Hierarchical scheduling, serial-batching, maximum cost
@article{RO_2021__55_1_135_0,
author = {He, Cheng and Lin, Hao and Li, Li},
title = {Hierarchical minimization of two maximum costs on a bounded serial-batching machine},
journal = {RAIRO. Operations Research},
pages = {135--140},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {1},
doi = {10.1051/ro/2020144},
mrnumber = {4228688},
zbl = {1471.90122},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020144/}
}
TY - JOUR AU - He, Cheng AU - Lin, Hao AU - Li, Li TI - Hierarchical minimization of two maximum costs on a bounded serial-batching machine JO - RAIRO. Operations Research PY - 2021 SP - 135 EP - 140 VL - 55 IS - 1 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020144/ DO - 10.1051/ro/2020144 LA - en ID - RO_2021__55_1_135_0 ER -
%0 Journal Article %A He, Cheng %A Lin, Hao %A Li, Li %T Hierarchical minimization of two maximum costs on a bounded serial-batching machine %J RAIRO. Operations Research %D 2021 %P 135-140 %V 55 %N 1 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020144/ %R 10.1051/ro/2020144 %G en %F RO_2021__55_1_135_0
He, Cheng; Lin, Hao; Li, Li. Hierarchical minimization of two maximum costs on a bounded serial-batching machine. RAIRO. Operations Research, Tome 55 (2021) no. 1, pp. 135-140. doi: 10.1051/ro/2020144
[1] , Scheduling Algorithms, 3rd edition. Springer, Berlin-Heidelberg (2001). | MR | Zbl
[2] and , Single machine batch scheduling with sequential job processing. IIE Trans. 33 (2001) 413–420. | DOI
[3] , and , Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost. Appl. Math. Comput. 332 (2018) 1–18. | MR | Zbl
[4] , , and , Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5 (1979) 287–326. | MR | Zbl | DOI
[5] , and , Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine. Found. Comput. Decis. Sci. 33 (2008) 369–376. | MR | Zbl
[6] , and , A DP algorighm for minimizing makespan and total completion time on a series-batching machine. Inf. Process. Lett. 109 (2009) 603–607. | MR | Zbl | DOI
[7] , and , , Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan. Central Eur. J. Oper. Res. 21 (2013) 177–186. | MR | Zbl | DOI
[8] , and , Bounded serial-batching scheduling for minimizing maximum lateness and makespan. Discrete Optim. 16 (2015) 70–75. | MR | Zbl | DOI
[9] , Single-machine scheduling to minimize a function of two or three maximum cost criteria. J. Algorithms 21 (1996) 415–433. | MR | Zbl | DOI
[10] , Study on several multicriteria scheduling problems. Master thesis, Henan University of Technology (2009).
[11] and , (1995) Scheduling groups of jobs on a single machine. Oper. Res. 43 (1995) 692–703. | MR | Zbl | DOI
Cité par Sources :
