Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines - Publication - Bridge of Knowledge

Search

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

Abstract

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

Citations

  • 0

    CrossRef

  • 0

    Web of Science

  • 2

    Scopus

Cite as

Full text

download paper
downloaded 48 times
Publication version
Accepted or Published Version
License
Creative Commons: CC-BY-NC-ND open in new tab

Keywords

Details

Category:
Articles
Type:
artykuł w czasopiśmie wyróżnionym w JCR
Published in:
Bulletin of the Polish Academy of Sciences-Technical Sciences no. 67, pages 31 - 36,
ISSN: 0239-7528
Language:
English
Publication year:
2019
Bibliographic description:
Pikies T., Kubale M.: Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines// Bulletin of the Polish Academy of Sciences-Technical Sciences. -Vol. 67, iss. 1 (2019), s.31-36
DOI:
Digital Object Identifier (open in new tab) 10.24425/bpas.2019.127335
Bibliography: test
  1. H.L. Bodlaender and K. Jansen, "On the complexity of sched- uling incompatible jobs with unit-times", Lecture Notes in Com- puter Science 711, (1993). open in new tab
  2. P. Brucker, Scheduling Algorithms, Fifth edition, Springer- Verlag Berlin Heidelberg, 2007. open in new tab
  3. M.I. Dessouky, B.J. Lageweg, J.K. Lenstra, and S.L. van de Velde, "Scheduling of identical jobs on uniform parallel ma- chines", Statistica Neerlandica 44, 115-123 (1990). open in new tab
  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). open in new tab
  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). open in new tab
  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). open in new tab
  7. K. Giaro, R. Janczewski, M. Kubale, and M. Małafiejski, "A 27/26-approximation algorithm for the chromatic sum col- oring of bipartite graphs", Lecture Notes in Computer Science 2462, 135-145 (2002). open in new tab
  8. K. Giaro, M. Kubale, and P. Obszarski, "A graph coloring ap- proach to scheduling of multiprocessor tasks on dedicated ma- chines with availability constraints", Discrete Applied Mathe- matics 157, 3625-3630 (2009). open in new tab
  9. M. Kubale, "Interval vertex-coloring of a graph with forbidden colors", Discrete Mathematics 74, 125-136 (1989). open in new tab
  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.
Sources of funding:
Verified by:
Gdańsk University of Technology

seen 200 times

Recommended for you

Meta Tags