Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines

• Autorzy: Pikies T. , Kubale Marek

Identyfikatory

DOI

10.24425/bpas.2019.127335

• Języki publikacji: EN

Abstrakty

EN

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|C_max. 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.

Słowa kluczowe

EN

approximation algorithm; graph coloring; incompatible job; polynomial algorithm; scheduling; uniform machine; unit-time jobs

PL

algorytm aproksymacyjny; kolorowanie grafów; algorytm wielomianowy; planowanie; praca jednostkowa

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2019
• Tom: Vol. 67, nr 1
• Strony: 31--36
• Opis fizyczny: Bibliogr. 11 poz., tab., rys.

Twórcy

autor

Pikies T.

• Department of Algorithms and System Modelling, Gdańsk University of Technology, ETI Faculty, Gabriela Narutowicza 11/12, 80-233 Gdańsk, Poland

autor

Kubale Marek

• Department of Algorithms and System Modelling, Gdańsk University of Technology, ETI Faculty, Gabriela Narutowicza 11/12, 80-233 Gdańsk, Poland

Bibliografia

• [1] H.L. Bodlaender and K. Jansen, ”On the complexity of scheduling incompatible jobs with unit-times”, Lecture Notes in Computer Science 711, (1993).
• [2] P. Brucker, Scheduling Algorithms, Fifth edition, Springer-Verlag Berlin Heidelberg, 2007.
• [3] M.I. Dessouky, B.J. Lageweg, J.K. Lenstra, and S.L. van de Velde, ”Scheduling of identical jobs on uniform parallel machines”, Statistica Neerlandica 44, 115–123 (1990).
• [4] 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).
• [5] 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).
• [6] 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).
• [7] K. Giaro, R. Janczewski, M. Kubale, and M. Małafiejski, ”A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs”, Lecture Notes in Computer Science 2462, 135‒145 (2002).
• [8] K. Giaro, M. Kubale, and P. Obszarski, ”A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints”, Discrete Applied Mathematics 157, 3625–3630 (2009).
• [9] M. Kubale, ”Interval vertex-coloring of a graph with forbidden colors”, Discrete Mathematics 74, 125‒136 (1989).
• [10] D.B. West, Introduction to Graph Theory, Pearson Education, Delhi India, 2002.
• [11] W. Willis, ”Bounds for the independence number of a graph”, Virginia Commonwealth University, 2011.

Uwagi

EN

The project has been partially supported by Gdańsk University of Technology, grant no. POWR.03.02.00-IP.08-00-DOK/16.

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).