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
-
0
Web of Science
-
2
Scopus
Cytuj jako
Pełna treść
pobierz publikację
pobrano 48 razy
- Wersja publikacji
- Accepted albo Published Version
- Licencja
-
otwiera się w nowej karcie
Słowa kluczowe
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
- Bibliografia: test
-
więcej (11) mniej
- 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
- P. Brucker, Scheduling Algorithms, Fifth edition, Springer- Verlag Berlin Heidelberg, 2007. otwiera się w nowej karcie
- 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
- 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
- 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
- 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
- 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
- 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
- M. Kubale, "Interval vertex-coloring of a graph with forbidden colors", Discrete Mathematics 74, 125-136 (1989). otwiera się w nowej karcie
- D.B. West, Introduction to Graph Theory, Pearson Education, Delhi India, 2002.
- W. Willis, "Bounds for the independence number of a graph", Virginia Commonwealth University, 2011.
- Źródła finansowania:
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 203 razy
Publikacje, które mogą cię zainteresować
Approximation algorithms for job scheduling with block-type conflict graphs
- H. Furmańczyk,
- T. Pikies,
- I. Sokołowska
- + 1 autorów
2024