TY - JOUR N2 - 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. L1 - http://www.czasopisma.pan.pl/Content/111100/PDF/03_031-036_00776_Bpast.No.67-1_06.02.20.pdf L2 - http://www.czasopisma.pan.pl/Content/111100 PY - 2019 IS - No. 1 EP - 36 DO - 10.24425/bpas.2019.127335 KW - approximation algorithm KW - graph coloring KW - incompatible job KW - polynomial algorithm KW - scheduling KW - uniform machine KW - unit-time job A1 - Pikies, T. A1 - Kubale, M. VL - 67 DA - 28.02.2019\ T1 - Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines SP - 31 UR - http://www.czasopisma.pan.pl/dlibra/publication/edition/111100 T2 - Bulletin of the Polish Academy of Sciences Technical Sciences ER -