PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments

Treść / Zawartość
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Rocznik
Strony
53--61
Opis fizyczny
Bibliogr. 6 poz., wykr., tab.
Twórcy
autor
  • Gdańsk University of Technology, Faculty of Electronics, Telecommunications and Informatics, Gdańsk, Poland
autor
  • Gdańsk University of Technology, Faculty of Electronics, Telecommunications and Informatics, Gdańsk, Poland
autor
  • Gdańsk University of Technology, Faculty of Electronics, Telecommunications and Informatics, Gdańsk, Poland
autor
  • Gdańsk University of Technology, Faculty of Electronics, Telecommunications and Informatics, Gdańsk, Poland
Bibliografia
  • [1] Chen, B.-L., Yen, C.-H., 2012. Equitable ∆-coloring of graphs, Discrete Mathematics. 312(9), pp. 1512–1517.
  • [2] Furmańczyk, H., Kubale, M., 2017a. Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines. Bulletin of the Polish Academy of Sciences: Technical Sciences, 65(1), pp. 29–34.
  • [3] Furmańczyk, H., Kubale, M., 2017b. Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines. Discrete Applied Mathematics (in Press).
  • [4] Kosowski, A., 2009. A note on the strength and minimum color sum of bipartite graphs. Discrete Applied Mathematics, 157(11), pp. 2552–2554.
  • [5] Małafiejski, M., Giaro, K., Janczewski, R., Kubale, M., 2004. Sum coloring of bipartite graphs with bounded degree. Algorithmica, 40(4), pp. 235–244.
  • [6] Steger, A., Wormald, N.C., 1999. Generating random regular graphs quickly. Combinatorics, Probability and Computing, 8(4), pp. 377–396.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-3d3530c4-30d6-4dfc-b6cc-8c46ad6b5d3a
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.