Search
Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines
Abstract
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.
Citations
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Authors (2)
Cite as
Full text
download paper
downloaded 69 times
- Publication version
- Accepted or Published Version
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
Bulletin of the Polish Academy of Sciences-Technical Sciences
no. 67,
pages 31 - 36,
ISSN: 0239-7528 - Language:
- English
- Publication year:
- 2019
- Bibliographic description:
- 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:
- Digital Object Identifier (open in new tab) 10.24425/bpas.2019.127335
- Sources of funding:
-
- Project nie dotyczy
- Verified by:
- Gdańsk University of Technology
seen 260 times
Recommended for you
Approximation algorithms for job scheduling with block-type conflict graphs
- H. Furmańczyk,
- T. Pikies,
- I. Sokołowska
- + 1 authors
2024