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.
Autorzy
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.24425/bpas.2019.127335
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuł w czasopiśmie wyróżnionym w JCR
- Język
- angielski
- Rok wydania
- 2019