Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines - Publikacja - MOST Wiedzy

Wyszukiwarka

Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines

Abstrakt

The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|p j = 1, G = bisubquartic|Cmax . The second one is Algorithm 3 which is 4-approximate for the problem Qm|p j = 1, G = bisubquartic|ΣC j , where m ∈ {2, 3, 4}. The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper.

Cytowania

  • 0

    CrossRef

  • 1

    Web of Science

  • 1

    Scopus

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
Bulletin of the Polish Academy of Sciences-Technical Sciences nr 67, strony 31 - 36,
ISSN: 0239-7528
Język:
angielski
Rok wydania:
2019
Opis bibliograficzny:
Pikies T., Kubale M.: Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines// Bulletin of the Polish Academy of Sciences-Technical Sciences. -Vol. 67, iss. 1 (2019), s.31-36
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.24425/bpas.2019.127335
Biblografia: test
  1. H.L. Bodlaender and K. Jansen, "On the complexity of sched- uling incompatible jobs with unit-times", Lecture Notes in Com- puter Science 711, (1993). otwiera się w nowej karcie
  2. P. Brucker, Scheduling Algorithms, Fifth edition, Springer- Verlag Berlin Heidelberg, 2007. otwiera się w nowej karcie
  3. M.I. Dessouky, B.J. Lageweg, J.K. Lenstra, and S.L. van de Velde, "Scheduling of identical jobs on uniform parallel ma- chines", Statistica Neerlandica 44, 115-123 (1990). otwiera się w nowej karcie
  4. S. Duraj, P. Kopeć, M. Kubale, T. and Pikies, "Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments", Decision Making in Manufacturing and Services 11, 53-61 (2017). otwiera się w nowej karcie
  5. H. Furmańczyk and M. Kubale, "Scheduling of unit-length jobs with bipartite incompatibility graphs of four uniform machines", Bull. Pol. Ac.: Tech. 65, 29-34 (2017). otwiera się w nowej karcie
  6. H. Furmańczyk and M. Kubale, "Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines", Discrete Applied Mathematics 234, 210-217 (2018). otwiera się w nowej karcie
  7. K. Giaro, R. Janczewski, M. Kubale, and M. Małafiejski, "A 27/26-approximation algorithm for the chromatic sum col- oring of bipartite graphs", Lecture Notes in Computer Science 2462, 135-145 (2002). otwiera się w nowej karcie
  8. K. Giaro, M. Kubale, and P. Obszarski, "A graph coloring ap- proach to scheduling of multiprocessor tasks on dedicated ma- chines with availability constraints", Discrete Applied Mathe- matics 157, 3625-3630 (2009). otwiera się w nowej karcie
  9. M. Kubale, "Interval vertex-coloring of a graph with forbidden colors", Discrete Mathematics 74, 125-136 (1989). otwiera się w nowej karcie
  10. D.B. West, Introduction to Graph Theory, Pearson Education, Delhi India, 2002.
  11. W. Willis, "Bounds for the independence number of a graph", Virginia Commonwealth University, 2011.
Źródła finansowania:
Weryfikacja:
Politechnika Gdańska

wyświetlono 54 razy

Publikacje, które mogą cię zainteresować

Meta Tagi