Autor: Pikies, T. - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines
Autorzy:: Pikies, T.
Kubale, Marek
Powiązania:: https://bibliotekanauki.pl/articles/201958.pdf
Data publikacji:: 2019
Wydawca:: Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:: approximation algorithm
graph coloring
incompatible job
polynomial algorithm
scheduling
uniform machine
unit-time jobs
algorytm aproksymacyjny
kolorowanie grafów
algorytm wielomianowy
planowanie
praca jednostkowa
Opis:: 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.
Źródło:: Bulletin of the Polish Academy of Sciences. Technical Sciences; 2019, 67, 1; 31-36
0239-7528
Pojawia się w:: Bulletin of the Polish Academy of Sciences. Technical Sciences
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments
Autorzy:: Duraj, S.
Kopeć, P.
Kubale, M.
Pikies, T.
Powiązania:: https://bibliotekanauki.pl/articles/376001.pdf
Data publikacji:: 2017
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: batch scheduling
bipartite graph
polynomial algorithm
uniform machines
Opis:: In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.
Źródło:: Decision Making in Manufacturing and Services; 2017, 11, 1-2; 53-61
1896-8325
2300-7087
Pojawia się w:: Decision Making in Manufacturing and Services
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja