Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines
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-appr...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Polish Academy of Sciences
2019-02-01
|
| Series: | Bulletin of the Polish Academy of Sciences: Technical Sciences |
| Subjects: | |
| Online Access: | https://journals.pan.pl/Content/111100/PDF/03_031-036_00776_Bpast.No.67-1_06.02.20.pdf |
| Summary: | 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|pj = 1, G = bisubquartic|Cmax. The second one is Algorithm 3 which is 4-approximate for the problem Qm|pj = 1, G = bisubquartic|ΣCj, 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. |
|---|---|
| ISSN: | 2300-1917 |