Geodesic
Bunch technique for $semionline$ with two groups of items
Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2019), pp. 134-138
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Bunch technique for semionline with two groups of items is proposed in this paper. Algorithm to solve this problem is to distribute items from the first group bunch approach and after that apply $LS$-algorithm to assign items from the second group. In order to prove the estimation of our algorithm is introduced different types of bunches to distribute all items from the first group such a way that only one of the entered types of bunches are obtained. During the second stage we use $LS$ with worst case performance is at most $\frac{17}{9}$.
Keywords: bunch technique; semionline; partition; scheduling; worst case performance. 
@article{BGUMI_2019_3_a11,
     author = {V. M. Kotov and N. S. Bogdanova},
     title = {Bunch technique for $semionline$ with two groups of items},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {134--138},
     year = {2019},
     volume = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a11/}
}
TY  - JOUR
AU  - V. M. Kotov
AU  - N. S. Bogdanova
TI  - Bunch technique for $semionline$ with two groups of items
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2019
SP  - 134
EP  - 138
VL  - 3
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a11/
LA  - ru
ID  - BGUMI_2019_3_a11
ER  - 
%0 Journal Article
%A V. M. Kotov
%A N. S. Bogdanova
%T Bunch technique for $semionline$ with two groups of items
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2019
%P 134-138
%V 3
%U http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a11/
%G ru
%F BGUMI_2019_3_a11
V. M. Kotov; N. S. Bogdanova. Bunch technique for $semionline$ with two groups of items. Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2019), pp. 134-138. http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a11/

[1] H. Kellerer, V. Kotov, M. G. Speranza, Z. Tuza, “Semi on-line algorithms for the partition problem”, Operations Research Letters, 21(5) (1997), 235–242 | DOI | MR | Zbl

[2] S. Albers, M. Hellwig, “Semi-online scheduling revisited”, Theoretical Computer Science, 443 (2012), 1–9 | DOI | MR | Zbl

[3] Y. He, G. Zhang, “Semi on-line scheduling on two identical machines”, Computing, 62(3) (1999), 179–187 | DOI | MR | Zbl

[4] M. Gabay, V. Kotov, N. Brauner, “Semi-online bin stretching with bunch techniques”, Theoretical Computer Science, 602 (2015), 103–113 | DOI | MR | Zbl

[5] H. Kellerer, V. Kotov, M. Gabay, “An efficient algorithm for semi-online multiprocessor scheduling with given total processing time”, Journal of Scheduling, 18(6) (2015), 623–630 | DOI | MR | Zbl