Bunch technique for semionline with two groups of items

Authors

Keywords:

bunch technique, semionline, partition, scheduling, worst case performance

Abstract

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 se cond 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 17/9.

Author Biographies

  • Vladimir M. Kotov, Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

    doctor of science (physics and mathematics), full professor; head of the department of discrete mathematics and algorithms, faculty of applied mathematics and computer science

  • Natallia S. Bogdanova, Sukhoi State Technical University of Gomel, 48 Kastryčnika Avenue, Gomel 246746, Belarus

    senior lecturer at the department of computer science, faculty of automation and information systems

References

  1. Kellerer H, Kotov V, Speranza MG, Tuza Z. Semi on-line algorithms for the partition problem. Operations Research Letters. 1997;21(5):235–242. DOI: 10.1016/ S0167-6377(98)00005-4.
  2. Albers S, Hellwig M. Semi-online scheduling revisited. Theoretical Computer Science. 2012;443:1– 9. DOI: 10.1016/jagm. 2012.03.031.
  3. He Y, Zhang G. Semi on-line scheduling on two identical machines. Computing. 1999;62(3):179 –187. DOI: 10.1007/s006070050020.
  4. Gabay M, Kotov V, Brauner N. Semi-online bin stretching with bunch techniques. Theoretical Computer Science. 2015;602: 103–113. DOI: 10.1016/j.tcs.2015.07.065.
  5. Kellerer H, Kotov V, Gabay M. An efficient algorithm for semi-online multiprocessor scheduling with given total processing time. Journal of Scheduling. 2015;18(6):623– 630. DOI: 10.1007/s10951-015-0430-4.

Downloads

Published

2019-11-20

Issue

No. 3 (2019): Journal of the Belarusian State University. Mathematics and Informatics

Section

Short Communications

License

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Kotov, V.M. and Bogdanova, N.S. 2019. Bunch technique for semionline with two groups of items. Journal of the Belarusian State University. Mathematics and Informatics. 3 (Nov. 2019), 134–138. DOI:https://doi.org/10.33581/2520-6508-2019-3-134-138.